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
1.3 Computers with Multiple Processors