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.