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:

 

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.

            [Beame]

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.

            [Attiya]

Reading material:

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.

 

Handouts:

·        General information (in Hebrew)

·        Home assignment #1 (weeks 1-3).

·        Home assignment #2 (weeks 4-7).