## An Introduction to Distributed AlgorithmsAn Introduction to Distributed Algorithms takes up some of the main concepts and algorithms, ranging from basic to advanced techniques and applications, that underlie the programming of distributed-memory systems such as computer networks, networks of workstations, and multiprocessors. Written from the broad perspective of distributed-memory systems in general it includes topics such as algorithms for maximum flow, program debugging, and simulation that do not appear in more orthodox texts on distributed algorithms.Moving from fundamentals to advances and applications, ten chapters—with exercises and bibliographic notes—cover a variety of topics. These include models of distributed computation, information propagation, leader election, distributed snapshots, network synchronization, self- stability, termination detection, deadlock detection, graph algorithms, mutual exclusion, program debugging, and simulation. All of the algorithms are presented in a clear, template- based format for the description of message-passing computations among the nodes of a connected graph. Such a generic setting allows the treatment of problems originating from many different application areas. The main ideas and algorithms are described in a way that balances intuition and formal rigor—most are preceded by a general intuitive discussion and followed by formal statements as to correctness complexity or other properties. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Fundamentals | 1 |

Intrinsic Constraints | 33 |

Models of Computation | 69 |

Basic Algorithms | 97 |

Basic Techniques | 117 |

Advances and Applications | 149 |

Graph Algorithms | 183 |

Resource Sharing | 219 |

Program Debugging | 253 |

Simulation | 291 |

323 | |

Author Index | 349 |

357 | |

### Other editions - View all

### Common terms and phrases

access the shared Action addition Algorithm A-PIF Algorithm A-Record-GlobaLState Algorithm A-Template assumption asynchronous algorithm Barbosa becomes true begin bit complexity Boolean variable broadcast buffers candidate channel chapter communication processor comp-msg complete graph complexity of Algorithm concurrently corresponding deadlock denoted detection dining philosophers problem directed cycle discussed in Section distributed algorithms distributed computation employed event execution exists expectedi false FIFO flow fork fragment function global state recording global termination Hi,nj identification indicate initial initiatedi Input iteration leader message complexity minimum spanning tree minimum-weight outgoing edge msgi MSGi(s neighbors Neigi networks of workstations nj's node nj node's number of messages origin^msg participate physical process physical system precedence graph problem propagation pulse queue re-execution receipt request respectively rithm Section 2.1 Send sent shared resources simulation synchronous model task techniques Theorem total order unconditional breakpoint undirected graph updated wormhole routing