Mathematics Colloquium: Emina Soljanin (Bell Labs)

Delay is one of the most important performance measures of a communication system. In scenarios as different as mobile, ad hoc, wireless networks and content distribution networks, delay is caused by seemingly very different random phenomena, which are often statistically similar. Thus, in a wide range of applications, the delay can be reduced by following the same idea. To help understand this idea, we consider the following scenario: Imagine an agent having a piece of information that he wants to communicate to his partner. The agent knows that his partner resides in an occupied city but does not want to be seen talking with him, or with anyone else on the street for a long time. The agent and his partner have a number of friends walking in the same city, who are willing to relay small pieces of information between the secret couple. Because of that, the agent decides to split his data in small chunks which he can then inconspicuously pass to his friends. To increase the data lifetime among his friends who are moving in an adverse environment, the agent also decides to make these data chunks redundant by erasure coding, that is, by generating a larger number of chunks s.t. the original data can be recovered based on any sufficiently large subset of the redundant chunks. Assuming that all participants in this multi-agent information transfer perform simple random walks over a finite, random, regular graph, and can exchange information only when they are on the same node of the graph, we describe how coding, at the expense of introducing redundancy and processing complexity, not only increases the lifetime of the data, but also reduces the average time necessary for the transfer of information between the agent and his partner.