T-79.192 Special Course in Theoretical Computer Science (2 cr)

Autumn 2002 -- Distributed Algorithmics

This autumn the course will take the form of a seminar on some algorithmic and complexity-theoretic issues that arise in distributed systems. Some specific topics to be studied include: fundamental algorithms in distributed systems; message complexity and energy efficiency of packet routing and topology control; efficient routing as combinatorial optimisation; competitive analysis of distributed online algorithms; self-stabilisation; algorithmics on the Web. (See blurb [pdf].)

[Current] [General] [Schedule] [Arrangements] [Material]

Previous years: [Autumn 2001] [Autumn 2000] [Autumn 1999] [Autumn 1998]

Current

• Slight change of schedule: talks on 16 Oct and 23 Oct have changed places.

General

• Time, place: Wednesdays, 12-2 p.m., seminar room TB353.
• Coordinator: Prof. Pekka Orponen, room TB207.
• Course assistant: M.Sc. (Tech.) Satu Virtanen, room TB213.
• Registration by TOPI, attending the first meeting, or by contacting the coordinator.
• Prerequisites: Basic knowledge of automata theory and formal methods (e.g. T-79.148), and competence in the design and analysis of algorithms (e.g. T-106.410).
• Assets: Familiarity with telecommunications and distributed systems (e.g. T-110.300, T-110.350, T-79.179).
• Credits: Seminar presentation plus archivable slides and/or paper 2 cr.

Tentative schedule

• 11 Sep: Opening, overview, handing out assigments (P.O.)
• 18 Sep: No seminar.
• 25 Sep: Guest lecture by Maarit Hietalahti: Ad hoc networks and information security (pdf)
  Key references: Becker & Wille 1998, Steiner et al. 1996.
• 2 Oct: Routing algorithms (Jan Lönnberg)
  Key references: Tel Ch. 4
  Slides in pdf. Feedback form.
• 9 Oct: Wave and traversal algorithms (Mikko Särelä)
  Key references: Tel Ch. 6
  Slides in pdf. Feedback form.
• 16 Oct: Topology control in ad hoc networks (Patrik Floreen, P.O.)
  Key references: Rajaraman 2002, Lloyd et al. 2002
  Slides in pdf (Floreen). Feedback form.
• 23 Oct: Cancelled.
• 30 Oct: Routing in ad hoc networks (Janne Lindqvist)
  Key references: Rajaraman 2002, Royer & Toh 1999
  Slides in ps. Slides in pdf. Feedback form.
• 6 Nov: Competitive analysis of online routing strategies (Antti Autere)
  Key references: Aiello et al. 1998, Awerbuch et al. 2001, 2002
  Feedback form.
• 13 Nov: Cancelled.
• 20 Nov: Fault-tolerance in asynchronous systems (Samuli Hinneri)
  Key references: Tel Ch. 14
  Slides in rtf. Feedback form.
• 27 Nov: Cancelled.
• 4 Dec: Self-stabilising algorithms (Satu Virtanen)
  Key references: Tel Ch. 17, Dolev 2000
  Slides in ps. Feedback form.

Arrangements

• Pointers to seminar material will be linked to the schedule above by coordinator. Printed copies of the material will be available for inspection in the course folder at the theory lab office (TB336).
• Electronic copy of presentation slides and/or seminar paper, together with any possible additional literature pointers mailed by presenter to coordinator by the presentation date. These will also be linked to the schedule above. A printed copy of the presentation will eventually be filed in the course folder.

Seminar material (tentative)

• W. Aiello, E. Kushilevitz, R. Ostrovsky, A. Rosen, Adaptive packet routing for bursty adversarial traffic. Proc. 30th Ann. ACM Symp. on Theory of Computing, 359-368. ACM, New York, NY, 1998.
• B. Awerbuch, P. Berenbrink, A. Brinkmann and C. Scheideler, Simple routing strategies for adversarial systems. Proc. 42nd Ann. IEEE Symp. on Foundations of Computer Science. IEEE Computer Society, Los Alamitos, CA, 2001.
• B. Awerbuch, A. Brinkmann and C. Scheideler, Anycasting and multicasting in adversarial systems: routing and admission control. Unpublished manuscript, May 2002.
• K. Becker, U. Wille, Communication complexity of group key distribution. Proc. 5th ACM Conference on Computer and Communications Security, 1-6. ACM, New York, NY, 1998.
• A. Borodin and R. El-Yaniv, Online Computation and Competitive Analysis. Cambridge University Press, 1998.
• S. Dolev, Self-Stabilization. The MIT Press, Cambridge, MA, 2000.
• S. Dolev, E. Schiller, J. Welch, Random walk for self-stabilizing group communication in ad-hoc networks. Proc. 21st Ann. ACM Symp. on Principles of Distributed Computing. ACM, New York, NY, 2002 (in press).
• A. Fiat and G. J. Woeginger (Eds.), Online Algorithms: The State of the Art. Lecture Notes in Computer Science 1442. Springer, Berlin, 1998.
• E. L. Lloyd, R. Liu, M. V. Marathe, R. Ramanathan, S. S. Ravi, Algorithmic aspects of topology control problems for ad hoc networks. Proc. 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing, 123-134. ACM, New York, NY, 2002.
• F. Meyer auf der Heide, C. Schindelhauer, K. Volbert and M. Grünewald, Congestion, energy and delay in radio networks. Preprint, 14 pp. Universität Paderborn, 2001.
• C. Papadimitriou, Algorithms, games, and the Internet. Proc. 33rd Ann. ACM Symp. on Theory of Computing, 749--753. ACM, New York, NY, 2001.
• R. Rajaraman, Topology control and routing in ad hoc networks: A survey. ACM SIGACT News 33:2 (June 2002), 60--73.
• E. M. Royer, C.-K. Toh, A review of current routing protocols for ad hoc mobile wireless networks. IEEE Personal Communications 6 (April 1999), 46-55.
• A. Srinivasan, C.-P. Teo, A constant-factor approximation algorithm for packet routing and balancing local vs. global criteria. SIAM J. Computing 30 (2000), 2051-2068.
• G. Tel, Introduction to Distributed Algorithms, 2nd Ed. Cambridge University Press, 2001.
• M. Steiner, G. Tsudik, M. Waidner, Diffie-Hellman key distribution extended to group communication. Proc. 3rd ACM Conference on Computer and Communications Security, 31-37. ACM Press, New York, NY, 1996.
• V. Vazirani, Approximation Algorithms. Springer, Berlin, 2001.