Modern Distributed Computing

Elective in Computer Networks II

(A. A. 2012/2013)

Syllabus

Distributed computing is essential in modern computing and communications systems. Examples are large-scale networks such as the Internet, low-power hand multiprocessors such as your new multi-core smartphone and tiny scale smart embedded devices distributed in our cities. Designing, engineering, deploying and operating current and future systems requires an understanding of the fundamental and practical aspects of distributed computation.

The course presents fundamental results of theoretical computer science establishing a solid basis on what is computational feasible, and providing essential algorithmic ideas and lower bound techniques.

The course is organized in the following parts:

  • Part 1: Static Synchronous Networks: Synchronous Message-passing Model, Definitions, Anonymous Leader Election, Impossibility Results, Symmetry Breaking Algorithms, Probabilistic Algorithms, Leader Election Algorithms, Broadcast, Convergecast, Lower Bounds.
  • Part 2: Failures: Link failures, Node failures, Impossibility Results, Agreement, Byzantine Failures, Failures in Asynchronous Systems.
  • Part 3: Static Asynchronous Networks: I/O Automata Model, Distributed Data Structures, Time, Clocks and Ordering of Events, Synchronizers, Global Predicates, Termination Detection.
  • Part 4: Dynamic Synchronous Networks: Dynamic Graph Model, Causal Influence, T-interval connectivity, Instantaneous Connectivity, Possibly Connected, Anonymous Networks, Unknown Networks, Counting, Naming.
  • Part 5: Stabilization: Definitions, Mutual Exclusion, Breadth First Search, Power Supply Technique.

Material

Slides

References

  1. Nancy A. Lynch, "Distributed Algorithms", Morgan Kaufmann Publishers, Inc., ISBN 1558603484 (a previous version of the material presented in the book is also available here)
  2. Hagit Attiya and Jennifer Welch, "Distributed Computing Fundamentals, Simulations, and Advanced Topics", McGraw-Hill Publishing Company, ISBN 0471453242
  3. Shlomi Dolev, "Self-Stabilization", The MIT Press, ISBN 0262041782
  4. O.Michail, I.Chatzigiannakis and P.Spirakis: New Models for Population Protocols. Synthesis Lectures on Distributed Computing Theory, edited by N.Lynch, Morgan & Claypool Publishers, ISBN 1608455890
  5. A.D. Kshemkalyani, M. Singhal, Distributed Computing: Principles, Algorithms, and Systems, Cambridge University Press, ISBN: 9780521189842