Distributed Computing Pearls. Gadi Taubenfeld

      

       Distributed Computing Pearls

       Synthesis Lectures on Distributed Computing Theory

      Editor

       Michel Raynal, University of Rennes, France and Hong Kong Polytechnic University

      Synthesis Lectures on Distributed Computing Theory is edited by Michel Raynal of the University of Rennes, France and Nancy Lynch of the Massachusetts Institute of Technology. The series publishes 50- to 150-page publications on topics pertaining to distributed computing theory. The scope largely follows the purview of premier information and computer science conferences, such as ACM PODC, DISC, SPAA, OPODIS, CONCUR, DialM-POMC, ICDCS, SODA, Sirocco, SSS, and related conferences. Potential topics include, but not are limited to: distributed algorithms and lower bounds, algorithm design methods, formal modeling and verification of distributed algorithms, and concurrent data structures.

      Distributed Computing Pearls

      Gadi Taubenfeld

      2018

      Decidability of Parameterized Verification

      Roderick Bloem, Swen Jacobs, Ayrat Khalimov, Igor Konnov, Sasha Rubin, Helmut Veith, and Josef Widder

      2015

      Impossibility Results for Distributed Computing

      Hagit Attiya and Faith Ellen

      2014

      Distributed Graph Coloring: Fundamentals and Recent Developments

      Leonid Barenboim and Michael Elkin

      2013

      Distributed Computing by Oblivious Mobile Robots

      Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro

      2012

      Quorum Systems: With Applications to Storage and Consensus

      Marko Vukolić

      2012

      Link Reversal Algorithms

      Jennifer L. Welch and Jennifer E. Walter

      2011

      Cooperative Task-Oriented Computing: Algorithms and Complexity

      Chryssis Georgiou and Alexander A. Shvartsman

      2011

      New Models for Population Protocols

      Othon Michail, Ioannis Chatzigiannakis, and Paul G. Spirakis

      2011

      The Theory of Timed I/O Automata, Second Edition

      Dilsun K. Kaynar, Nancy Lynch, Roberto Segala, and Frits Vaandrager

      2010

      Principles of Transactional Memory

      Rachid Guerraoui and Michal Kapalka

      2010

      Fault-tolerant Agreement in Synchronous Message-passing Systems

      Michel Raynal

      2010

      Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems

      Michel Raynal

      2010

      The Mobile Agent Rendezvous Problem in the Ring

      Evangelos Kranakis, Danny Krizanc, and Euripides Markou

      2010

      Copyright © 2018 by Morgan & Claypool

      All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means—electronic, mechanical, photocopy, recording, or any other except for brief quotations in printed reviews, without the prior permission of the publisher.

      Distributed Computing Pearls

      Gadi Taubenfeld

       www.morganclaypool.com

      ISBN: 9781681733487 paperback

      ISBN: 9781681733494 PDF

      ISBN: 9781681733517 ePub

      ISBN: 9781681733500 hardcover

      DOI 10.2200/S00845ED1V01Y201804DCT014

      A Publication in the Morgan & Claypool Publishers series

       SYNTHESIS LECTURES ON DISTRIBUTED COMPUTING THEORY

      Lecture #14

      Series Editor: Michel Raynal, University of Rennes, France and Hong Kong Polytechnic University

      Founding Editor: Nancy Lynch, Massachusetts Institute of Technology

      Series ISSN

      Print 2155-1626 Electronic 2155-1634

       Distributed Computing Pearls

      Gadi Taubenfeld

      The Interdisciplinary Center, Herzliya

       SYNTHESIS LECTURES ON DISTRIBUTED COMPUTING THEORY #14

       ABSTRACT

      Computers and computer networks are one of the most incredible inventions of the 20th century, having an ever-expanding role in our daily lives by enabling complex human activities in areas such as entertainment, education, and commerce. One of the most challenging problems in computer science for the 21st century is to improve the design of distributed systems where computing devices have to work together as a team to achieve common goals.

      In this book, I have tried to gently introduce the general reader to some of the most fundamental issues and classical results of computer science underlying the design of algorithms for distributed systems, so that the reader can get a feel of the nature of this exciting and fascinating field called distributed computing. The book will appeal to the educated layperson and requires no computer-related background. I strongly suspect that also most computer-knowledgeable readers will be able to learn something new.

       KEYWORDS

      algorithms, distributed algorithms, synchronization, agreement, consensus, synchronous, asynchronous, randomized algorithms, Byzantine agreement, choice coordination, the see-saw puzzle, the two lovers problem, the two generals problem, the too much bread problem, deadlock, dining philosophers, mutual exclusion, barrier synchronization, crash failures, Byzantine failures

      To Miki,the love of my life.

       Contents

       Preface

       Acknowledgments

       1 Distributed Computing

       1.1 Winds of Change

       1.2 The Internet

       1.3 Computers with Multiple Processors

       1.4 Synchronization