Distributed Algorithms

A BRICS Mini-Course
June 12 and 13, 1996

Lectures by
Richard Tan

Course Contents

The course aims at introducing the non-expert to the field. Some general knowledge of algorithms and complexity suffices.

Each Lecture is basically self-contained and can be attended separately.

Wednesday June 12, 1996, 10:15-12:00 in Colloquium D4 Lecture I Introduction and Models. Election on a Ring: Asynchronous algorithms Synchronous algorithms Lower Bound results
Wednesday June 12, 1996, 14:15-16:00 in Colloquium D4 Lecture II Election on complete graphs Minimum Spanning Trees on general graphs
Thursday June 13, 1996, 10:15-12:00 in Colloquium D4 Lecture III Global Algorithms: Termination Detection Snapshots
Thursday June 13, 1996, 14:15-16:00 in Colloquium D4 Lecture IV Fault-Tolerance: Benign Failures Byzantine Failures Self-stabilization

J. Misra and K. M. Chandy: Parallel Program Design: A Foundation, Addison-Wesley, 1988.
Nancy Lynch: Distributed Algorithms, Morgan Kaufman Publishers, 1996.
Gerard Tel: Introduction to Distributed Algorithms, Cambridge University Press, 1994.

G. Lelann: Distributed systems - towards a formal approach, Inf. Proc. Let., 1977, pp. 155-160.
E. Chang & R. Roberts: An improved algorithm for decentralized extrema-finding in circular configurations of processes, Comm. ACM, vol. 22, 1979, pp. 281-283.
W. Franklin:On an improved algorithm for decentralized extrema finding in circular configurations of processors, Comm. ACM, vol 25, 1982, pp.336-337.
G. Peterson: An O(n\log(n)) unidirectional algorithm for the circular extrema problem, ACM TOPLAS, vol. 4, 1982, pp. 758-762.
G. Frederickson & N. Lynch: Electing a leader in a synchronous ring, J. ACM, vol. 34, 1987, pp. 98-115.
J. Pachl, E. Korach & D. Rotem: Lower bounds for distributed maximum finding algorithms, J. ACM, vol. 30, 1984, pp.905-918.

Y. Afek & E. Gafni: Time and message bounds for election in synchronous and asynchronous complete networks, SIAM J. Computing, vol. 20, 1991, pp. 376-394.
R. Gallager, P. Humblet & P. Spira: A distributed algorithm for minimum-weight spanning trees, ACM TOPLAS, vol. 5, 1983, pp. 66-77.

E. Dijkstra & C. Scholten: Termination detection for diffusing computations, Inf. Proc. Lett. vol. 11, 1980, pp. 1-4.
E. Dijkstra, E. Feijen & A. van Gasteren: Derivation of a termination detection algorithm for distributed computations, Inf. Proc. Lett., vol. 16, 1983, pp. 217-219.
F. Mattern: Algorithms for distributed termination detection, Distributed Computing, vol. 2, 1987, pp. 161-175.
K. Chandy & L. Lamport: Distributed Snapshots: determining global states of distributed systems, ACM Tran. Comp. Sys., vol. 3, 1985, pp. 63-75.

M. Pease, R. Shostak & L. Lamport: Reaching agreement in the presence of faults, J. ACM, vol. 27, 1980, pp. 228-234.
L. Lamport, R. Shostak & M. Pease: The Byzantine generals problem, ACM TOPLAS, vol. 4, 1982, pp.382-401.
D. Dolev & H. Strong: Authenticated algorithms for Byzantine agreement, SIAM J. Computing, vol. 12, 1983, pp. 656-666.
M. Fischer, N. Lynch & M. Merritt: Easy impossibility proofs for distributed consensus problem, Info. Proc. Lett., vol.14, 1982, pp. 183-186.
E. Dijkstra: Self-stabilization in spite of distributed control, Comm. ACM, vol. 17, 1974, pp. 643-644.