Time and place: Monday 12:30-14:30. Taub 6.
This course studies lower bounds and impossibility results for various problems (and models) in distributed computing. Emphasis will be placed on techniques.
Week-by-week course plan:
- Week 1: Introduction. Why lower bounds. Administration.
Shifting arguments, used to bound operation cost for linearizability and sequential consistency.
[Attiya and Welch]
- Week 2: Shifting arguments applied to prove a lower bound on clock synchronization precision.
Scaling plus scenario arguments, used to prove n>3f, for clock synchronization in the presence of Byzantine failures.
[Lundelius and Lynch] [Fisher, Lynch and Merritt]
- Week 3: Fan-in arguments, bounding the influence of processes inputs.
A log n lower bound on the step complexity of computing OR (folklore).
A log n lower bound on the time complexity of wait-free approximate agreement.
[Attiya, Lynch and Shavit]
- Week 4: Paritioning arguments, bounding the amount of information acquired.
A log n lower bound on the step complexity of collecting information.
A log n lower bound on the step complexity of synchronous snapshots.
[Brodsky and Fich]
- Week 5, Part I: Information theoretic arguments, for objects with limited write-contention.
A log n lower bound on the solo step complexity of weak test&set.
[Attiya, Fich and Kaplan]
- Week 5, Part II: Arguing about causality in asynchronous systems.
A Diam(s-1) lower bound on the step complexity of the s-session problem.
[Arjomandi, Fischer and Lynch]
[Attiya and Welch, Section 6.2.2]
- Week 6: Combinatorial arguments.
An Omega(m) lower bound on update time for atomic snapshots.
[Israeli and Shirazi]
- Week 7: Covering arguments.
An Omega(n) lower bound on registers and steps for implementing a counter out of swap objects.
[Jayanti, Tan and Toueg]
- Week 8:
- Week 9: Covering arguments and potential decisions.
An Omega(sqrt(n)) space lower bound for randomized and obstruction-free consensus: the anonymous case.
[Fich, Herlihy and Shavit]
- Week 10: Covering arguments and potential decisions (continued).
An Omega(sqrt(n)) space lower bound for randomized and obstruction-free consensus: the nonanonymous case.
[Fich, Herlihy and Shavit]
- Week 11: Bivalence arguments.
A lower bound on the number of rounds for randomized consensus in synchronous message-passing systems.
[Bar-Joseph and Ben-Or]
- Week 12: Bivalence arguments and connectivity arguments.
A lower bound on the total work for randomized consensus in asynchronous shared-memory systems.
- Week 13: Graph theoretic arguments (based on topology).
Impossibility of wait-free k-set consensus in a system with k+1 processes.
Papers from the scientific literature. The following survey paper is a good start:
- Faith Ellen Fich and Eric Ruppert, Hundreds of impossibility proofs for distributed computing, Distributed Computing, Volume 16, Issues 2-3, pp. 121 – 163.
Background material can be found in:
- Hagit Attiya and Jennifer L. Welch, Distributed Computing: Fundamentals, Simulations, and Advanced Topics, John Wiley and Sons, Inc.; 2nd edition, 2004.
- Nancy Lynch, Distributed Algorithms, Morgan Kaufmann, 1997.