Coding-Based Distributed Storage in Large-Scale Networks

Speaker: Prof. Emina Soljanin , Bell Labs, Lucent and ALGO, EPFL


We consider large-scale networks with N nodes, out of which K are in possessi on, (e.g., have sensed or collected in some other way) K data packets. In the sc enarios in which network nodes are vulnerable because of, for example, limited e nergy or a hostile environment, it is desirable to disseminate the acquired info rmation throughout the network so that each of the N nodes stores one (possibly coded) packet so that the original K source packets can be recovered later in a computationally simple way from any K(1+e) nodes for some small e > 0. We presen t two Fountain codes based distributed algorithms solving this problem. Unlike a ll previously developed schemes, our algorithms are truly distributed, that is, nodes do not know N, K or connectivity in the network, except in their own neigh borhoods, and they do not maintain any routing tables.