DC - Distributed Computing (2008 - 2009)
Up one level
- Upon successful completion of this course, students should be able to:
- build formal models of distributed system;
- differentiate between synchronous and asynchronous models;
- understand the assumptions and limitations underlying models of distributed systems;
- describe the more relevant problems in distributed systems;
- reason about distributed algorithms;
- design new distributed algorithms;
- invoke impossibility results to avoid wasting time trying to solve an unsolvable problem;
- prove impossibility results.
- Synchronous networks:
- Formal model (lockstep rounds) and proof methods
- Basic algorithms: Leader Election, Spanning Trees
- Agreement in synchronous networks:
- The abstract consensus problem
- Agreement with process and link failures
- Byzantine agreement
- Asynchronous networks:
- Formal models (I/O automata,TLA) and proof methods
- Basic algorithms: (revisited)
- Logical time in asynchronous networks:
- Causality, real time and logical time
- Vector clocks and version vectors
- Stable properties:
- ∗ Distributed termination ∗ Global snapshots ∗ Deadlock detection
- Agreement in asynchronous networks:
- Impossibility of fault-tolerant consensus
- Failure detectors and indulgence
- Unreliable channels
- Agreement problems
N. Lynch. Distributed Algorithms. Morgan-Kaufmann, 1996.
L. Lamport. Time, clocks and the ordering of events in a distributed system. Communication of the ACM 21, no.7, July 1978.
F. Mattern. Virtual time and global states of distributed systems. In Z. Yang, and T. Marsland (eds.) Global States and Time in Distributed Systems, IEEE, 1994.
L. Lamport. The part-time parliament. Transactions on Computer Systems 16, no.2, May 1989.
T. Chandra and S. Toueg. Unreliable failure detectors for reliable distributed systems. Journal of the ACM, Volume 43, Issue 2, March 1996.
T. Chandra, V. Hadzilacos, and S. Toueg. The weakest failure detector for solving consensus. In Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, 1992.
P. Dutta and R. Guerraoui. The inherent price of indulgence. Distributed Computing 18(1), Springer, 2005.
J. B. Almeida, P. S. Almeida, C. Baquero. Bounded version vectors. In Rachid Guerraoui, editor, Proceedings of DISC 2004: 18th international symposium on distributed computing, number 3274 in LNCS, pages 102–116. 2004. Springer Verlag.
J. Pereira, R. Oliveira. The mutable consensus protocol. Proc. 23rd international symposium on reliable distributed systems, pages 218-227. Florianopolis, Brazil, 2004. IEEE, IEEE Computer Society.
V. Hadzilacos, S. Toueg, Fault-tolerant broadcasts and related problems, In Distributed systems (2nd Ed.), ACM Press/Addison-Wesley Publishing Co., New York, NY, 1993.