materialy: Tel = Gerard Tel: Introduction to Distributed Algorithms Ly = Nancy A. Lynch: Distributed Algorithms Le = Frank Thomson Leighton: Introduction to parallel algorithms and architectures: arrays, trees, hypercubes sylabus: - prehlad distribuovanych systemov - sietovy model [ Tel, kap. 2 ] - prehladavanie grafov (shout-echo ) [ Tel, 6.3, 6.4: Traversal ] - volba sefa v uplnom grafe, horny + dolny odhad na pocet sprav [ dolny odhad: E. Korach, S. Moran, S. Zaks: Tight Lower and Upper Bounds for Some Distributed Algorithms for a Complete Network of Processors, Proceedings of the third annual ACM symposium on Principles of distributed computing, August 1984, pp. 199-207 ] - volba sefa na kruhu (chang-roberts, analyza priemerneho pripadu) [ Ernest Chang, Rosemary Roberts: An Improved Algorithm for Decentralized Extrema-Finding in Circular Configurations of Processes, Communications of the ACM, 22(5), 1979, pp. 281-283 ] - volba sefa na kruhu ( n log n sprav v najhorsom pripade + dolny odhad ) [ Ly : 15.1 ] - volba sefa v lubovolnych grafoch (GHS, KKM) [ Tel , kap. 7 ] - uplny graf: vplyv zmyslu pre orientaciu [ G. Singh: Leader election in complete networks, Proceedings of the eleventh annual ACM symposium on Principles of distributed computing, October 1992, pp. 179-190 ] - kruh: vplyv synchronnosti [ Greg N. Frederickson, Nancy A. Lynch: Electing a Leader in a Synchronous Ring, JACM, 34(1), 1987, pp. 98-115 ] - routovanie, pocitanie najkratsich ciest, algoritmus Netchange, hierarchicke routovanie [ Tel: kap. 4 ] - routovanie paketov [ Le : 1.7 ] - odolnost voci chybam [Ly: kap 5,6 ]