Broadly speaking, a distributed computing system is a set of computers that collectively solve a problem. This encompasses environments ranging from a tightly coupled multiprocessor to wide area networks connecting computers over large distances. Such systems are finding increasing use in todays applications including airline reservations systems, weather prediction, real-time process control, and protein interaction identification for drug design. However, factors like asynchrony that come with a system consisting of many independent computers make distributed computing quite challenging. The possibility of failure of some computers in the system further complicates the task. This course will study these issues in distributed computing through models, algorithms and lower bounds, with an emphasis on fundamental problems.

Text: Distributed Computing, by H. Attiya and J. Welch, 2nd edition, Wiley Interscience, 2004.
           Papers from current literature

Prerequisites: Basic ideas in algorithm design and analysis

Tentative Topics: basic models and complexity measures, leader election, mutual exclusion, consensus, fault-tolerance, broadcast and multicast, causality, synchonization, simulations among models, sensor network and mobile computing issues.

Basis for grading: