Lower Bound Techniques in Distributed Computing

Lecturers:

Hagit Attiya
Faith Ellen Fich

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:

  1. Week 1: Introduction. Why lower bounds. Administration.
    Shifting arguments, used to bound operation cost for linearizability and sequential consistency.
    [Attiya and Welch]
  2. 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]
  3. 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]
  4. Week 4: Paritioning arguments, bounding the amount of information acquired.
    A log n lower bound on the step complexity of collecting information.
    [Beame]
    A log n lower bound on the step complexity of synchronous snapshots.
    [Brodsky and Fich]
  5. 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]
  6. 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]
  7. Week 6: Combinatorial arguments.
    An Omega(m) lower bound on update time for atomic snapshots.
    [Israeli and Shirazi]
  8. 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]
  9. Week 8:
  10. 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]
  11. 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]
  12. 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]
  13. Week 12: Bivalence arguments and connectivity arguments.
    A lower bound on the total work for randomized consensus in asynchronous shared-memory systems.
  14. Week 13: Graph theoretic arguments (based on topology).
    Impossibility of wait-free k-set consensus in a system with k+1 processes.
    [Attiya]

Reading material:

Papers from the scientific literature. The following survey paper is a good start:

Background material can be found in:

Handouts: