BRICS · Contents · Programme · References

**A BRICS Mini-Course**

**June 12 and 13, 1996**

**Lectures by
Richard Tan
**

**
**

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 IIntroduction and Models.

- Election on a Ring:

- Asynchronous algorithms
- Synchronous algorithms
- Lower Bound results

- Election on a Ring:
### 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

- Global Algorithms:
### Thursday June 13, 1996, 14:15-16:00 in Colloquium D4

### Lecture IV

- Fault-Tolerance:

- Benign Failures
- Byzantine Failures
- Self-stabilization

- Fault-Tolerance:

- Hagit Attiya: Lecture Notes on Distributed Algorithms is available electronically.

- 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.