lunduniversity.lu.se

Software Development and Environments

Computer Science | Faculty of Engineering, LTH

Denna sida på svenska This page in English

Distributed Algorithms

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-12 Lucas room
    S1: Intro, Distribution, and Abstractions (Ch 1)
    Seminar leaders: Jörn Janneck, Amr Ergawy
    slides
  • Date: Tue April 8 10-12 Lucas room
    S2: Processes and Links (Sections 2.1, 2.2, and 2.4)
    Seminar leaders: Amr Ergawy
    slides
  • Date: Mon April 15 10-12 Lucas 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-12 Lucas 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-12 Lucas 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-12 Lucas 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-12 Lucas 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-12 Lucas 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-12 Lucas 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-12 Lucas 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-12 E: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-12 Lucas room
    S12: Vector Clocks
    Seminar leaders: Gustav Cedersjö
    slides