A modern study of information must take into account the fact that information is distributed among many agents at different locations. Agents can communicate among themselves, subject to a variety of different possible communication assumptions. Agents may also interact with the physical world. The configuration may be dynamic: agents may move, and their communication capabilities and external interactions may change over time.

In such a setting, we would like to understand basic capabilities for the agents to communicate, to compute, and to coordinate to perform real-world activities. We plan to investigate the way information flows through a distributed network and to study the type and amount of information necessary to solve classical distributed tasks in dynamic networks.

Focused problems for the short term:

We will develop new models of communication, computation, and coordination based on dynamic graphs, with active agents associated with the graph nodes. We will define new metrics to capture constraints on the graphs and their patterns of change, and to evaluate system performance. Using these models and metrics, we will study algorithms and lower bounds for solving a variety of problems, including problems of global message broadcast, counting, and function computation. We will study relationships between different problems, trying to determine which problems can be reduced to which others, and with what overhead. We will also consider how various constraints on dynamic graphs, and on the ability for the agents to control changes to the graphs, affect the algorithmic and lower bound results.

We will study the amount of information agents must exchange to solve various problems, and what information about the network they must acquire to do so. To this end, we will consider the problem of information dissemination, in which each agent receives an input, and all agents must collect all inputs. Information dissemination is a powerful primitive, which allows agents to compute any function of their states; for example, if each agent takes a measurement of the local temperature, using information dissemination each agent can collect the other agents' measurements and compute the average temperature.

It was previously shown by members of our group that information dissemination can be solved in dynamic networks, assuming that the communication network is always connected. However, the complexity of solving information dissemination is not currently known. Further, it is not clear whether full information dissemination is required to compute functions such as the average or minimum of the agents' measurements, or whether it is sufficient to exchange less information. We intend to study these questions.

We are also interested in the effect global information about the network can have on the efficiency of distributed computation. In recent work on wireless and ad-hoc networks it is frequently assumed that agents are privy to global parameters such as the total number of agents or the maximum node degree in the communication graph. We will study the degree to which such information is helpful, and determine the complexity of acquiring global knowledge about the network.