|
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]
- Slight change of schedule: talks on 16 Oct and 23 Oct
have changed places.
- 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.
- 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.
- 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.
[TCS main]
[Contact Info]
[Personnel]
[Research]
[Publications]
[Software]
[Studies]
[News Archive]
[Links]
Latest update: 23 December 2004.
Pekka Orponen.
|