# Lecturers:

**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,
, John Wiley and Sons, Inc.; 2*Distributed Computing: Fundamentals, Simulations, and Advanced Topics*^{nd}edition, 2004. - Nancy Lynch,
, Morgan Kaufmann, 1997.*Distributed Algorithms*

# Handouts:

- General information (in Hebrew)
- Home assignment #1 (weeks 1-3).
- Home assignment #2 (weeks 4-7).