Instructor: M. Mavronicolas
  Room: FST 01-106
  Telephone: 22-892702
Back to Main Page Class Contract Assignments and Solutions Exams





Conclusion of DSM: Lower bounds for linearizability using the shifting technique.


[1] Attiya and Welch, Chapter 9, Sections 9.4.


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.


[1] Attiya and Welch, Chapter 9, Sections 9.1, 9.2 and 9.3 (except for 9.3.1).


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.


[1] Attiya and Welch, Section 6.3.5


The averaging clock synchronization algorithm of Lundelius and Lynch.


[1] Lecture notes (transparencies)

[2] Attiya and Welch, Section 6.3 (except for 6.3.5)


Discussion on the analysis of distributed decision-making protocols. Reexamination of algorithm complexity and problem complexity; how to prove bounds on them.


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


Finish up the proof that the optimal, oblivious decision-making algorithm is symmetric and uniform. Conclusion of the discussion on distributed, decision-making algorithms.


Continuation of the analysis for distributed decision-making protocols. Derivation of probabilistic lemmas from the geometric lemmas (for volume computations). The model of distributed decision-making. The particular case of no communication, and its subcases of oblivious and non-oblivious protocols. Definition of winning probability.


Finish up the proof of the impossibility for finite-size, low-contention switching networks implementing the RMW operation.


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 finite-state switching network to implement a monotone group.


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


Continuation of the discussion on monotone groups (n-wise independence). Proof that every monotone group is n-wise independent. General model of a distributed system. The Unique Serialization Lemma. Linearizability and Sequential Consistency.


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

  • Counting networks (some basic constructions and impossibility results).
  • 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).
  • 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).
  • Analysis of the rounds complexity of the Lattice Agreement algorithm presented in previous lecture.


  • 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.)

  • 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


  • 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.


  • The Message Passing Model

  • Rings (anonymous and eponymous, uniform and non-uniform, synchronous and asynchronous)

  • The Leader Election Problem

    • Non-existence of an anonymous algorithm

    • Eponymous algorithm with Θ(n2) messages