Distributed Algorithms

Distributed Algorithms

2 January 2021 | Jukka Suomela
This book provides an introduction to the theory of distributed algorithms, covering models of computing, algorithm design and analysis, and computability and computational complexity. It discusses various models, including the PN model, the LOCAL model, and the CONGEST model, and presents algorithms for solving distributed graph problems such as colouring paths, bipartite matching, and vertex covers. The book also explores negative results, such as the impossibility of 2-colouring paths in sub-linear time, and introduces concepts like locality and Ramsey theory. It includes detailed algorithms, their analysis, and exercises for readers to practice. The book is suitable for students and researchers in computer science and distributed systems.This book provides an introduction to the theory of distributed algorithms, covering models of computing, algorithm design and analysis, and computability and computational complexity. It discusses various models, including the PN model, the LOCAL model, and the CONGEST model, and presents algorithms for solving distributed graph problems such as colouring paths, bipartite matching, and vertex covers. The book also explores negative results, such as the impossibility of 2-colouring paths in sub-linear time, and introduces concepts like locality and Ramsey theory. It includes detailed algorithms, their analysis, and exercises for readers to practice. The book is suitable for students and researchers in computer science and distributed systems.
Reach us at info@study.space
[slides and audio] Distributed Algorithms