Distributed Algorithms

The primary source will be the book Distributed Algorithms by Prof. Nancy Lynch.

[Lynch] = Lynch, Nancy. Distributed Algorithms . Burlington, MA: Morgan Kaufmann, 1996. ISBN: 9781558603486.

[Attiya and Welch] = Attiya, Hagit, and Jennifer Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics . 2nd ed. New York, NY: Wiley-Interscience, 2004. ISBN:9780471453246.

This is another textbook on distributed algorithms, initially published a little after the Lynch book. It now has a second edition. The material covered overlaps quite a lot with the Lynch book, though Attiya and Welch do cover some topics, like clock synchronization, that Lynch does not cover. The style is a little less formal.

[Herlihy and Shavit] = Herlihy, Maurice, and Nir Shavit. The Art of Multiprocessor Programming . Burlington, MA: Morgan Kaufmann, 2008. ISBN: 9780123705914.

This undergraduate textbook covers basic algorithms and techniques for multiprocessor programming.

[Guerraoui and Kapalka] = Guerraoui, Rachid, and Michal Kapalka. Transactional Memory: The Theory . San Rafael, CA: Morgan and Claypool, 2010. ISBN: 9781608450114.

Kaynar, Disun, Nancy Lynch, Roberto Segala, and Frits Vaandrager. The Theory of Timed I/O Automata . 2nd ed. San Rafael, CA: Morgan and Claypool, 2010. ISBN: 9781608450022.

SES #: 1 · TOPICS: Course overview. Synchronous networks. Leader election in synchronous ring networks. · READINGS: [Lynch] Chapters 1 and 2, sections 3.1 to 3.5.

SES #: 2 · TOPICS: Leader election in rings. Basic computational tasks in general synchronous networks: leader election. Breadth-first search. Broadcast and convergecast. Shortest paths. · READINGS: [Lynch] Section 3.6, and sections 4.1 to 4.3.

SES #: 3 · TOPICS: Spanning trees. Shortest paths (Bellman-Ford). Minimum spanning trees. Maximal independent sets (summary). · READINGS: [Lynch] Sections 4.3 to 4.5 (skip 4.5.3).

SES #: 4 · TOPICS: Fault-tolerant consensus. Link failures: the two generals problem. Process failures (stopping, Byzantine). Algorithms for agreement with stopping and Byzantine failures. Exponential information gathering. · READINGS: [Lynch] Sections 5.1 and 6.1 to 6.3.

Aguilera, Marcos Kawazoe, and Sam Toueg. “A Simple Bivalency Proof that t -Resilient Consensus Requires t +1 Rounds.” Information Processing Letters 71, nos. 3-4 (August 1999): 155-158.

6 · k -set-agreement. Approximate agreement. Distributed commit. · [Lynch] Chapter 7.

7 · Asynchronous distributed computing. Formal modeling of asynchronous systems using interacting state machines (I/O automata). Proving correctness of distributed algorithms. · [Lynch] Chapter 8.

8 · Non-fault-tolerant algorithms for asynchronous networks. Leader election, breadth-first search, shortest paths, broadcast and convergecast. · [Lynch] Chapters 14 and 15.

9 · Spanning trees. Gallager et al . minimum spanning trees.

Gallager, R. G., P. A. Humblet, and P. M. Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (January 1983): 66-77.

10 · Synchronizers. Synchronizer applications. Synchronous vs . asynchronous distributed systems. · [Lynch] Chapter 16.

[Lynch] Chapter 18.

Mattern, Friedemann. “Virtual Time and Global States of Distributed Systems.” In Parallel and Distributed Algorithms: Proceedings of the International Workshop on Parallel and Distributed Algorithms (Chateau de Bonas, Gers, France, October, 1988) . Edited by Michel Cosnard, et al. Amsterdam, The Netherlands: North Holland, 1989, 215-226. ISBN: 9780444873675. Reprint, Yang, Zhonghua, and T. Anthony Marsland, eds. “Virtual Time and Global States of Distributed Systems.” In Global States and Time in Distributed Systems . Los Alamitos, CA: IEEE Computer Society Press, 1994, pp. 123-133. ISBN: 9780818653001.

12 · Stable property detection. Distributed termination. Global snapshots. Deadlock detection. · [Lynch] Chapter 19.

13 · Asynchronous shared-memory systems. The mutual exclusion problem. Mutual exclusion algorithms: Dijkstra’s algorithm, Peterson’s algorithm, and Lamport’s Bakery algorithm. · [Lynch] Chapter 9 and sections 10.1 to 10.7.

[Herlihy and Shavit] Chapter 7.

[Lynch] Chapter 11.

Mellor-Crummey, John M., and Michael L. Scott. “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.” ACM Transactions on Computer Systems 9, no. 1 (February 1991): 21-65.

Magnussen, Peter, Anders Landin, and Erik Hagersten. “Queue Locks on Cache Coherent Multiprocessors.” Proceedings of the 8th International Symposium on Parallel Processing , 1994, pp. 165-171.

[Lynch] Chapters 11 and 12.

Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. “Impossibility of Distributed Consensus with One Faulty Process.” Journal of the Association for Computing Machinery 32, no. 2 (April 1985): 374-382.

17 · Atomic objects · [Lynch] Chapter 13 (sections 13.1 and 13.2).

18 · Atomic snapshot algorithms. Atomic read/write register algorithms. · [Lynch] Chapter 13 (sections 13.3 and 13.4).

19 · List algorithms: locking algorithms, optimistic algorithms, lock-free algorithms, lazy algorithms. · [Herlihy and Shavit] Chapter 9.

[Herlihy and Shavit] Chapter 18.

[Guerraoui and Kapalka] Chapters 1 to 4.

Herlihy, Maurice. “Wait-Free Synchronization.” ACM Transactions on Programming Languages and Systems 13, no. 1 (January 1991): 124-149.

[Attiya and Welch] Chapter 15.

22 · Wait-free vs. f -fault-tolerant atomic objects. Boosting fault-tolerance.

Borowsky, Elizabeth, Eli Gafni, Nancy Lynch, and Sergio Rajsbaum. “The BG Distributed Simulation Algorithm.” Distributed Computing 14 (2001): 127-146.

Attie, Paul, Rachid Guerraoui, Petr Kouznetsov, Nancy Lynch, and Sergio Rajsbaum. “The Impossibility of Boosting Distributed Service Resilience.” Submitted for journal publication, September 2009.

Chandra, Tushar D., Vassos Hadzilacos, Prasad Jayanti, and Sam Toueg. “Generalized Irreducibility of Consensus and the Equivalence of t -Resilient and Wait-Free Implementations of Consensus.” SIAM Journal on Computing 34, no. 2 (2004): 333-357.

[Lynch] Chapter 17.

Lamport, Leslie. “The Part-Time Parliament.” ACM Transactions on Computer Systems 16, no. 2 (May 1998): 133-169. Also available as Research Report 49, Digital Equipment Corporation Systems Research Center, Palo Alto, CA, September 1989.

24 · Self-stabilizing algorithms · [Dolev] Chapter 2.

[Lynch] Chapters 23 to 25.

[Attiya and Welch] Section 6.3 and chapter 13.

In each of the years 2000-2009, a prize has been awarded to a research paper that has had a strong impact on research in the area of distributed algorithms. The prize was originally called the “PODC Influential Paper Award.” After the death of Edsger Dijkstra, one of the pioneers of the field, in August 2002, the prize was renamed the “Dijkstra Prize.”

Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. “Impossibility of Distributed Consensus with One Faulty Process.” Journal of the Association for Computing Machinery 32, no. 2 (April 1985): 374-382.

Dijkstra, Edsger W. “Self-Stabilizing Systems in Spite of Distributed Control.” Communications of the Association for Computing Machinery 17, no. 11 (November 1974): 643-644.

Herlihy, Maurice. “Wait-Free Synchronization.” ACM Transactions on Programming Languages and Systems 13, no. 1 (January 1991): 124-149.

Gallager, R. G., P. A. Humblet, and P. M. Spira. “A Distributed Algorithm for Minimum-Weight Spanning Trees.” ACM Transactions on Programming Languages and Systems 5, no. 1 (January 1983): 66-77.

Mellor-Crummey, John M., and Michael L. Scott. “Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors.” ACM Transactions on Computer Systems 9, no. 1 (February 1991): 21-65.

Dwork, Cynthia, Nancy Lynch, and Larry Stockmeyer. “Consensus in the Presence of Partial Synchrony.” Journal of the Association for Computing Machinery 35, no. 2 (April 1988): 288-323.

Awerbuch, Baruch, and David Peleg. “Sparse Partitions.” Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, St. Louis, Missouri, October, 1990, pp. 503-513.

Halpern, Joseph, and Yoram Moses. “Knowledge and Common Knowledge in a Distributed Environment.” Journal of the Association for Computing Machinery 37, no. 3 (July 1990): 549-587.

Mattern, Friedemann. “Virtual Time and Global States of Distributed Systems.” In Parallel and Distributed Algorithms: Proceedings of the International Workshop on Parallel and Distributed Algorithms (Chateau de Bonas, Gers, France, October, 1988) . Edited by Michel Cosnard, et al. Amsterdam, The Netherlands: North Holland, 1989, 215-226. ISBN: 9780444873675. Reprint, Yang, Zhonghua, and T. Anthony Marsland, eds. “Virtual Time and Global States of Distributed Systems.” In Global States and Time in Distributed Systems . Los Alamitos, CA: IEEE Computer Society Press, 1994, pp. 123-133. ISBN: 9780818653001.

Fidge, Colin. “Logical Time in Distributed Computing Systems.” IEEE Computer 24, no. 8 (August 1991): 28-33.

Chaudhuri, Soma. “More Choices Allow More Faults : Set Consensus Problems in Totally Asynchronous Systems.” Information and Computation 105, no. 1 (July 1993): 132-158.

The following paper and thesis chapter present a new, fundamental lower bound for the time required to achieve mutual exclusion.

Fan, Rui, and Nancy Lynch. “An Ω*(n log n)* Lower Bound on the Cost of Mutual Exclusion.” Proceedings of the Twenty-Fifth Annual Symposium on Principles of Distributed Computing (PODC'06), Denver, Colorado, (July 22-26, 2006). Best Student Paper Award.

Fan, Rui. “Mutual Exclusion.” Chapter 4 in Lower Bounds in Distributed Computing. PhD dissertation, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, February 2008.

Jayanti, Prasad. “Robust Wait-Free Hierarchies.” Journal of the Association for Computing Machinery 44, no. 4 (July 1997): 592-614.

Chandra, Tushar D., Vassos Hadzilacos, Prasad Jayanti, and Sam Toueg. “Generalized Irreducibility of Consensus and the Equivalence of t -Resilient and Wait-Free Implementations of Consensus.” SIAM Journal on Computing 34, no. 2 (2004): 333-357.

Borowsky, Elizabeth, Eli Gafni, Nancy Lynch, and Sergio Rajsbaum. “The BG Distributed Simulation Algorithm.” Distributed Computing 14 (2001): 127-146.

Attie, Paul, Rachid Guerraoui, Petr Kouznetsov, Nancy Lynch, and Sergio Rajsbaum. “The Impossibility of Boosting Distributed Service Resilience.” Submitted for journal publication, September 2009.

Chandra, Tushar Deepak, and Sam Toueg. “Unreliable Failure Detectors for Reliable Distributed Systems.” Journal of the Association for Computing Machinery 43, no. 2 (March 1996): 225-267.

Lamport, Leslie. “The Part-Time Parliament.” ACM Transactions on Computer Systems 16, no. 2 (May 1998): 133-169. Also available as Research Report 49, Digital Equipment Corporation Systems Research Center, Palo Alto, CA, September 1989.

Chandra, Tushar Deepak, Vassos Hadzilacos, and Sam Toueg. “The Weakest Failure Detector for Solving Consensus.” Journal of the Association for Computing Machinery 43, no. 4 (July 1996): 685-722.

Guerraoui, Rachid, Maurice Herlihy, Petr Kouznetsov, Nancy Lynch, and Calvin Newport. “On the Weakest Failure Detector Ever.” Distributed Computing 21, no. 5 Special Issue (February 2009): 353-366.

The brand-new Herlihy-Shavit textbook covers the principles of multiprocessor programming quite thoroughly:

Herlihy, Maurice, and Nir Shavit. The Art of Multiprocessor Programming . Burlington, MA: Morgan Kaufmann, 2008. ISBN: 9780123705914.

Magnussen, Peter, Anders Landin, and Erik Hagersten. “Queue Locks on Cache Coherent Multiprocessors.” Proceedings of the 8th International Symposium on Parallel Processing , 1994, pp. 165-171.

Guerraoui, Rachid, and Michal Kapalka. Transactional Memory: The Theory . San Rafael, CA: Morgan and Claypool, 2010. ISBN: 9781608450114.

Dolev, Shlomi. Self-Stabilization . Cambridge, MA: MIT Press, 2000. ISBN: 9780262041782.

The Attiya-Welch book contains a chapter on basic clock synchronization algorithms:

Attiya, Hagit, and Jennifer Welch. Distributed Computing: Fundamentals, Simulations, and Advanced Topics . 2nd ed. New York, NY: Wiley-Interscience, 2004. ISBN: 9780471453246.

The following paper and thesis contain a lower bound on “gradient” clock synchronization. The thesis chapter is more up-to-date than the journal paper.

Fan, Rui, and Nancy Lynch. “Gradient Clock Synchronization.” Distributed Computing 18, no. 4 (March 2006): 255-266.

Fan, Rui. “Gradient Clock Lower Bound.” Chapter 2 in Lower Bounds in Distributed Computing . PhD dissertation, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA, February 2008.

Kaynar, Disun, Nancy Lynch, Roberto Segala, and Frits Vaandrager. The Theory of Timed I/O Automata . 2nd ed. San Rafael, CA: Morgan and Claypool, 2010. ISBN: 9781608450022.

Readings that cover the material for each class will be announced ahead of time. For most classes, these will be sections from the textbook. For some classes, they will be research papers from the supplementary reading list. Reading a research paper will generally take more time than reading sections from the textbook, so be prepared to put in the extra time. We expect students to read the assigned material ahead of time and to come to class prepared to discuss it.