Skip to content


Personal tools
You are here: Home » Teaching » Distributed Computing » DC - Distributed Computing (2008 - 2009)

DC - Distributed Computing (2008 - 2009)

Document Actions
Up one level
This course aims at providing the theoretical foundations of distributed systems. It is targeted to graduate students and researchers wishing to advance the state-of-the-art in distributed systems. The course is technology agnostic and the abstractions presented are independent of any given technology. Although theoretical in nature, the course will also benefit students doing a more practical research.

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.

DC - Distributed Computing (2008 - 2009) Slides
DC - Distributed Computing (2008 - 2009) Papers
Created by als
Last modified 2009-04-15 11:22 PM
Outros Recursos
« March 2015 »
Su Mo Tu We Th Fr Sa
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        

Powered by Plone

This site conforms to the following standards: