Abstract

Imagine an agent having a piece of information that he wants to communicate to his partner. The agent knows that his partner resides in a certain part of 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 part of the city, and 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 inconspicuously pass to his friends. To increase persistency of the data among the friends who are moving in an adverse environment, the agent also decides to make these data chunks redundant by using erasure correcting codes. Assuming that all participants in this storing and retrieving process 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 persistence of the data, but also reduces the average time necessary for the transfer of information between the agent and his partner.