Description

The course provides students with the foundation knowledge to understand, analysis and design distributed algorithms. This shall be useful to a wide variety of research topics from the theory of distributed algorithms to protocol design, e.g. broadcasting protocols for discovery purposes in ad-hoc networks.

The course is based on the course Distributed Systems – Advanced Course that is taught at ICT-KTH

The course topics include:

• Models of distributed algorithms
• Fault Tolerance Abstractions and Failure Detectors
• Reliable Broadcast
• Causal Broadcast
• Shared Memory
• Consensus
• Atomic Broadcast
• Byzantine Fault-Tolerance
• Virtual Synchrony

When

Spring 2013, Starting on April 2nd (see the schedule below for details). To sign up for the course email one of the course organizers.

Credits, Workload and Form

Credits:7.5hp

Workload and form:

Each student is required to give two seminars about two of the course topics, see the schedule section below. It is also possible that a team of two students gives four seminars.

The seminar leader(s) are required to prepare the slides of their presentation by studying the appointed book sections. Also, she/he/they may use any additional sources they see relevant.

The bottom line is that taking responsibility of a seminar is taking responsibility of being a teacher for other course participants for that seminar topic, so please study the relevant book sections well and do not only depend on reading any external slides which are prepared by already expert teachers for their own use.

Additionally, each PhD student has to deeply study at least three papers, and to write a summary of each that is no less than one-page long. Below is a recommended papers list. By 15th of July 2013, each PhD student has to email all his summaries to another PhD student who may come back with comments to the writer and perhaps have a pair discussion if necessary. Below is a list of reviewers based on alphabetical order:
Reviewer->Writer
--------------------------------
Amr -> Björn
Björn -> Gustav
Gustav -> Maj
Maj -> Sardar
Sardar -> Usman
Usman -> Amr

Also, please forward the email with the summaries and that with the comments to Jörn.

The dealine to submit the summaries and the reviews is 15th of July, 2013.

Course Organizers

Jörn Janneck (AT cs.lth.se), Amr Ergawy (AT cs.lth.se)

Course Material

Christian Cachin, Rachid Guerraoui, and Luis Rodrigues,
Introduction to Reliable and Secure Distributed Programming,
Springer, 2011,
ISBN 3-642-15259-7

Suggested papers:

Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. 1988.
Consensus in the presence of partial synchrony.
J. ACM 35, 2 (April 1988), 288-323.
DOI=10.1145/42282.42283

Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1983.
Impossibility of distributed consensus with one faulty process.
In Proceedings of the 2nd ACM SIGACT-SIGMOD symposium on Principles of database systems (PODS '83). ACM, New York, NY, USA, 1-7.
DOI=10.1145/588058.588060

Leslie Lamport. 1978.
Time, clocks, and the ordering of events in a distributed system.
Commun. ACM 21, 7 (July 1978), 558-565.
DOI=10.1145/359545.359563

Colin J. Fidge. 1988.
Timestamps in Message-Passing Systems That Preserve the Partial Ordering.
Australian Computer Science Communications, Vol. 10, No. 1, pp. 56-66, February 1988

Friedemann Mattern. 1988.
Virtual Time and Global States of Distributed Systems.
Proceedings of the International Workshop on Parallel and Distributed Algorithms, France, October 1988

Sarin, S.K., Lynch, N.A., 1987.
Discarding Obsolete Information in a Replicated Database System.
Software Engineering, IEEE Transactions on (Volume:SE-13, Issue:1).
DOI=10.1109/TSE.1987.232564

M. A. Drummond and Valmir C. Barbosa. 2003.
On reducing the complexity of matrix clocks. Parallel Comput. 29, 7 (July 2003), 895-905.
DOI=10.1016/S0167-8191(03)00066-8

Gene T.J. Wuu and Arthur J. Bernstein. 1984
Efficient solutions to the replicated log and dictionary problems.
In Proceedings of the third annual ACM symposium on Principles of distributed computing (PODC '84). ACM, New York, NY, USA, 233-242.
DOI=10.1145/800222.806750

Prerequisites

It is recommended to have background in algorithms and distributed/networked processing/systems.

Schedule

• Date: Tue April 2 10-12Lucas room
  S1: Intro, Distribution, and Abstractions (Ch 1)
  Seminar leaders: Jörn Janneck, Amr Ergawy
  slides
  
• Date: Tue April 8 10-12Lucas room
  S2: Processes and Links (Sections 2.1, 2.2, and 2.4)
  Seminar leaders: Amr Ergawy
  slides
  
• Date: Mon April 15 10-12Lucas room
  S3: Timing assumptions, Abstracting time, An introduction to distributed system models (Ch 2.5, 2.6, 2.7)
  Seminar leaders: Maj Stenmark
  slides
  
• Date: Mon April 22 10-12Lucas room
  S4: Broadcast algorithms ascending in reliability. Probabilistic broadcast (Ch 3.1 to 3.8, inclusive)
  Seminar leaders: Björn A Johnsson
  slides
  
• Date: Mon April 29 10-12Lucas room
  S5: Algorithms that adds ordering to broadcasting and that survives arbitrary faults (Ch 3.9 to 3.12 inclusive)
  Seminar leaders: Gustav Cedersjö
  slides
  
• Date: Mon May 6 10-12Lucas room
  S6: - Discussing register models without recovery from failures (Ch 4.1 to 4.4 inclusive)
  Seminar leaders: Björn A Johnsson
  slides
  
• Date: Mon May 13 10-12Lucas room
  S7: - Discussing register models with recovery from failures (Ch 4.5 to 4.8 inclusive)
  Seminar leaders: Maj Stenmark
  slides
  
• Date: Mon May 20 10-12Lucas room
  S8: Consensus models without failure recovery, A failure recovery Consensus algorithm (Ch 5.1 to 5.4 inclusive)
  Seminar leaders: Sardar Muhammad Sulaman
  slides
  
• Date: Mon May 27 10-12Lucas room
  S9: - Continuing with failure recovery consensus algorithms, starting from randomized consensus and ending with surviving arbitrary faults (Ch 5.5 to 5.7 inclusive)
  Seminar leaders: Sardar Muhammad Sulaman
  slides
  
• Date: Mon June 3 10-12Lucas room
  S10: - Starting with consensus based broadcast algorithms, and ending with introducing fast consensus algorithms (Ch 6.1 to 6.5 inclusive)
  Seminar leaders: Usman Mazhar Mirza
  slides
  
• Date: Mon June 10 10-12E:2116
  S11: - More consensus based algorithms, e.g. atomic commitment and group membership (Ch 6.7 to 6.8 inclusive)
  Seminar leaders: Usman Mazhar Mirza
  slides
  
• Date: Mon June 17 10-12Lucas room
  S12: Vector Clocks
  Seminar leaders: Gustav Cedersjö
  slides