Distributed algorithms

CS-451 / 8 credits

Teacher: Guerraoui Rachid

Language: English

Summary

Computing is nowadays distributed over several machines, in a local IP-like network, a cloud or a P2P network. Failures are common and computations need to proceed despite partial failures of machines or communication links. This course will study the foundations of reliable distributed computing.

Content

Reliable broadcast       
Causal Broadcast   
Total Order Broadcast   
Consensus   
Non-Blocking Atomic Commit  
Group Membership, View Synchrony
Terminating Reliable Broadcast   
Shared Memory in Message Passing Systems
Byzantine Fault Tolerance 
Self Stabilization
Population protocols   (models of mobile networks)

Bitcoin, Blockchain

Distributed Machine Learning

Gossip

Keywords

Distributed algorithms, checkpointing, replication, consensus, atomic broadcast, ditributed transactions, atomic commitment, 2PC, Machine Learning

Learning Prerequisites

Required courses

Basics of Algorithms, networking and operating systems

Recommended courses

The lecture is orthogonal to the one on concurrent algorithms: it makes a lot of sense to take them in parallel.

Learning Outcomes

By the end of the course, the student must be able to:

  • Choose an appropriate abstraction to model a distributed computing problem
  • Specify the abstraction
  • Present and implement it
  • Analyze its complexity
  • Prove a distributed algorithm
  • Implement a distributed system

Teaching methods

Ex cathedera

Lectures, exercises and practical work

Assessment methods

Final exam (theory)

Project (practice)

Resources

Ressources en bibliothèque

Notes/Handbook

Reliable and Secure Distributed Programming
Springer Verlag
C. Cachin, R. Guerraoui, L. Rodrigues

Moodle Link

In the programs

  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Distributed algorithms
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Lab: 3 Hour(s) per week x 14 weeks
  • Type: mandatory
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Distributed algorithms
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Lab: 3 Hour(s) per week x 14 weeks
  • Type: mandatory
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Distributed algorithms
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Lab: 3 Hour(s) per week x 14 weeks
  • Type: mandatory
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Distributed algorithms
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Lab: 3 Hour(s) per week x 14 weeks
  • Type: mandatory
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Distributed algorithms
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Lab: 3 Hour(s) per week x 14 weeks
  • Type: mandatory
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Distributed algorithms
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Lab: 3 Hour(s) per week x 14 weeks
  • Type: mandatory
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Distributed algorithms
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Lab: 3 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Distributed algorithms
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Lab: 3 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Distributed algorithms
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Lab: 3 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Distributed algorithms
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Lab: 3 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Distributed algorithms
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Lab: 3 Hour(s) per week x 14 weeks
  • Type: optional
  • Exam form: Written (winter session)
  • Subject examined: Distributed algorithms
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Lab: 3 Hour(s) per week x 14 weeks
  • Type: optional
  • Semester: Fall
  • Exam form: Written (winter session)
  • Subject examined: Distributed algorithms
  • Courses: 2 Hour(s) per week x 14 weeks
  • Exercises: 1 Hour(s) per week x 14 weeks
  • Lab: 3 Hour(s) per week x 14 weeks
  • Type: optional

Reference week

Related courses

Results from graphsearch.epfl.ch.