Petr Kuznetsov, S3 INFRES, Telecom ParisTech

You have made your dead system on so large a scale that you do not yourselves know how or where it will hit. That's the paradox! Things have grown incalculable by being calculated. G. K. Chesterton, ``The Return of Don Quixote'', 1926

The curse of concurrency in computing is its complexity. Even a small-scale concurrent system may expose an amazingly complex behavior that would make it very challenging to formally reason about. But we have to meet the challenge! Due to inherent limitations of centralized computing, all computing systems nowadays is becoming distributed, ranging from Internet-scale services to multiprocessors. Therefore, understanding the principles of concurrency is indispensable in all aspects of designing and engineering modern computing systems. The main challenge here is to balance correctness of the system's executions with its availability and efficiency, in the presence of possible misbehavior of the system components and the environment (such as faults and asynchrony).

Students who complete this module will learn how to design concurrent algorithms, reason about their correctness, and derive matching complexity bounds. The primary focus of the module is on understanding of the foundations of concurrent computing. The module will start with well-established theory of fault-tolerant shared-memory computations, highlight the elegant modeling approach based on algebraic topology, and explore more recent and advanced abstractions, such as transactional memory.

Modeling distributed computing: safety and liveness; linearizability and wait-freedom; consensus and state-machine replication; algebraic topology and distributed computing; failure detectors; transactional memory

The course will be taught in English.

12h45-15h45, Bat. Sophie Germain, Room 1008

The schedule above is subject to change. The first class is taking place on December 12, 2013, 12:45-15:45, Bat. Sophie Germain, room to be specified later

None, though some maturity in mathematical reasoning and algorithms is expected.

• Introduction
• Synchronization, blocking and non-blocking
• Safety and liveness
• Read-write registers
• Atomic snapshots
• Immediate snapshots
• Consensus and set agreement
• Shelling Computability
• Consensus number and universal construction
• Atomicity assertion (Tromp's algorithm)
• Transactional memory

• Quiz 1
• Relative liveness: example
• Quiz 2
• Quiz 3

• Lecture notes on robust concurrent computing, in progress, last revision September 2013 pdf
• Lynch, N: Distributed Algorithms. Morgan Kaufmann Publishers, 1996.
• H. Attiya, J. Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics (2nd edition). Wiley. 2004
• M. Herlihy and N. Shavit. The art of multiprocessor programming. Morgan Kaufman, 2008
• R. Guerraoui, M. Kapalka. Principles of Transactional Memory. Morgan and Claypool Publishers, 2010

2-18-1, 2-18-2, 2-11-1, 2-11-2