1st Max-Planck Advanced Course on the Foundations of Computer Science
Saarbrücken,
Germany, August 31- September 4, 2000
Familiarity with the concept of amortized analyses using potential functions., see e.g.
R.E. Tarjan, "Amortized computational complexity," SIAM Journal on Algebraic and Discrete Methods, 6:306-318, 1985.
A. Borodin and R. El-Yaniv, Online computation and
competitive analysis, Cambridge University Press, 1998.
See
pages 9--10.
Prerequisites
Distributed Computing: shared memory model, linearizability, wait-freedom, randomization, shared objects (registers, test&set, compare&swap, read-modify-write), simulation, problems and algorithms (mutual exclusion, consensus and leader election, atomic snapshot)
Lower Bounds: information theory lower bound, adversary argument
Bibliography
The material on distributed computing can be found in either of the following standard textbooks on the theory of distributed computing:
H. Attiya and J. Welch,
Distributed Computing: Fundamentals, Simulations, and Advanced
Topics, McGraw Hill, 1998.
See parts of chapters 4, 5, 7,
10, and 14.
N. Lynch, Distributed
Algorithms, Morgan-Kaufmann, 1996.
See parts of chapters 9,
10, 12, and 13.
The material on lower bounds can be found in many computer algorithm textbooks. Here are some examples:
S. Baase, Computer
Algorithms: Introduction to Design and Analysis, Addison-Wesley,
1978.
See parts of sections 1.4, 1.5, and 2.4.
E. Horowitz and S. Sahni,
Fundamentals of Computer Algorithms, Computer Science
Press, 1984.
See chapter 10.
D. Knuth, The Art of Computer Programming, volume 3,
Addison-Wesley, 1973.
See section 5.3.
A course in Algorithms.
Familiarity with Approximation Algorithms, Randomized Algorithms and Linear Programming.
Mathematical maturity.
Elementary knowledge of complexity.
Elementary knowledge of Markov chains and random walks.
Elementary knowledge of graph theory.
More information, if needed, can be obtained via e-mail at <adfocs00@mpi-sb.mpg.de>.