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

Readings:

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

Readings:

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

Readings:

[1] Attiya and Welch, Section 6.3.5

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)

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.

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

• 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 non-uniform, synchronous and asynchronous)

• The Leader Election Problem

  • Non-existence of an anonymous algorithm

  • Eponymous algorithm with Θ(n²) messages