Theory of Distributed Systems

The Theory of Distributed Systems group, led by Prof. Nancy Lynch, works on a wide range of problems in distributed computing theory. Much of our work studies algorithms and lower bounds for typical problems that arise in distributed systems---like resource allocation, implementing shared memory abstractions, and reliable communication. Until recently, the focus was on rather static wired systems (see Lynch's book on Distributed Algorithms). However, in the past few years, most of our work has been on dynamic systems, in which the participants may come and go. We are now especially interested in wireless mobile ad hoc networks. In mobile networks, one wants to solve many of the same problems as in wired networks; however, new problems arise (e.g., getting messages to a particular geographical location, or controlling robots or cars), and new powers can be assumed (e.g., a node may know its approximate location). These new considerations provide interesting challenges for theoretical work.