02/12/2005 
Conclusion of DSM: Lower bounds for
linearizability using the shifting technique.
Readings:
[1] Attiya and Welch, Chapter 9,
Sections 9.4.

25/11/2005 
Distributed Shared memory (DSM).
Consistency conditions for DSM, including sequential
consistency and linearizability. Upper bounds for
sequential consistency: the Local Reads and Local Wirtes
algorithms.
Readings:
[1] Attiya and Welch, Chapter 9,
Sections 9.1, 9.2 and 9.3 (except for 9.3.1).

22/11/2005 
The technique of shifting executions
to prove lower bounds in distributed computing,
Application to prove a matching lower bound on the skew
achieved by the averaging clock synchronization
algorithm of Lundelius and Lynch.
Readings:
[1] Attiya and Welch, Section 6.3.5

18/11/2005 
The averaging clock synchronization algorithm of
Lundelius and Lynch.
Readings:
[1] Lecture notes (transparencies)
[2] Attiya and Welch, Section 6.3
(except for 6.3.5)

15/11/2005 
Discussion on the analysis of
distributed decisionmaking protocols. Reexamination of
algorithm complexity and problem complexity; how to
prove bounds on them.

11/11/2005 
More on the theoretical model of
messagepassing. Precise definition of message
complexity and time complexity. The simple message
flooding algorithm as a toy example for the analysis of
the complexities.

08/11/2005 
Finish up the proof that the
optimal, oblivious decisionmaking algorithm is
symmetric and uniform. Conclusion of the discussion on
distributed, decisionmaking algorithms.

04/11/2005 
Continuation of the analysis for
distributed decisionmaking protocols. Derivation of
probabilistic lemmas from the geometric lemmas (for
volume computations). The model of distributed
decisionmaking. The particular case of no
communication, and its subcases of oblivious and
nonoblivious protocols. Definition of winning
probability.

21/10/2005 
Finish up the proof of the
impossibility for finitesize, lowcontention switching
networks implementing the RMW operation.

18/10/2005 
Continuation of the discussion on
the model of switching networks: Contention measures
(register bottleneck, switch bottleneck). Switching
networks implementing monotone groups. The Monotone
Linearizability Lemma (without proof). Started the
impossibility result for finitestate switching network
to implement a monotone group.

14/10/2005 
The model of switching networks:
basic definitions, processes, tokens and switches;
states, configurations and executions. Outputs in
switching networks.

11/10/2005 
Continuation of the discussion on
monotone groups (nwise independence). Proof that
every monotone group is nwise independent.
General model of a distributed system. The Unique
Serialization Lemma. Linearizability and Sequential
Consistency.

07/10/2005 
Introduction to distributed data
structures. Implementation of shared memory operations
via (distributed) networked data structures. Monotone
operations and monotone groups.

04/10/2005 
 Counting networks (some basic
constructions and impossibility results).

30/09/2005 
 Impossibility of the Byzantine
Agreement problem for n ≤ 3f: Reduction of the
smallest case (n = 3, f = 1) to the general case.
 Introduction to the asynchronous
shared memory model of distributed computation:
 Types of registers.
 Read & Modify & Write
registers.
 Counters.
 Introduction to counting networks
(small example).

27/09/2005 
 Finish up the analysis of the
rounds complexity for the Lattice Agreement algorithm.
 Impossibility of the Byzantine
Agreement problem for n ≤ 3f: The smallest case (n=3,
f=1).

23/09/2005 
 Analysis of the rounds complexity
of the Lattice Agreement algorithm presented in previous
lecture.

20/09/2005 

Introduction to
Failures , Crash Failures.

Agreement Problems
(general).

Lattice Agreement
Problem.

Synchronous Algorithm
for the Lattice Agreement Problem in the Presence of
Breakdown Errors. (See
Exercise.)

16/09/2005 
 Completion of our proof of the
lower bound Ω(lgn)
messages for the Leader Election Problem in the
asynchronous, eponymous ring.
 Algorithm with Θ(n)
messages for the Leader Election Problem in the
eponymous, synchronous ring

13/09/2005 

Leader Election
Algorithm for the asynchronous eponymous ring with
Θ(n logn) messages

The lower bound
Ω(n logn) messages for the
Leader Election Problem in the (asynchronous, eponymous)
ring.

09/09/2005 

The Message Passing
Model

Rings (anonymous and eponymous,
uniform and nonuniform, synchronous and asynchronous)

The Leader Election
Problem
