Academic
Publications
Algebraic gossip: a network coding approach to optimal multiple rumor mongering

Algebraic gossip: a network coding approach to optimal multiple rumor mongering,10.1145/1148663.1148678,IEEE Transactions on Information Theory,Suprat

Algebraic gossip: a network coding approach to optimal multiple rumor mongering   (Citations: 81)
BibTex | RIS | RefWorks Download
We study the problem of simultaneously disseminating multiple messages in a large network in a decentralized and distributed manner. We consider a network with n nodes and k (k = O(n)) messages spread throughout the network to start with, but not all nodes have all the messages. Our communication model is such that the nodes communicate in discrete-time steps, and in every time-step, each node communicates with a random communication partner chosen uniformly from all the nodes (known as the random phone call model). The system is bandwidth limited and in each time-step, only one message can be transmitted. The goal is to disseminate rapidly all the messages among all the nodes. We study the time required for this dissemination to occur with high probability, and also in expectation. We present a protocol based on random linear coding(RLC) that disseminates all the messages among all the nodes in O(n) time, which is order optimal, if we ignore the small overhead associated with each transmission. The overhead does not depend on the size of the messages and is less than 1% for k = 100 and messages of size 100 KB. We also consider a store and forwardmechanism without coding, which is a natural extension of gossip-based dissemination with one message in the network. We show that, such an uncoded scheme can do no better than a sequential approach (instead of doing it simulta- neously) of disseminating the messages which takes ( nln(n)) time, since disseminating a single message in a gossip network takes (ln( n)) time.
Journal: IEEE Transactions on Information Theory - TIT , vol. 52, no. 6, pp. 2486-2507, 2006
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...From a more theoretical perspective, Deb et al. [12] are the first to analyze the performance of using random network coding with random gossiping...
    • ...Deb et al. [12] have shown that, if each peer linearly combines all the blocks it has already received using random coefficients and transmits this coded block to its target, the time for all n peers to receive all k blocks is ck þ Oð ffiffiffi k p logk lognÞ rounds, where c is a constant...
    • ...As each peer chooses random targets from the entire network to communicate with, it is implicitly assumed in [12] that the P2P overlay topologyVdefined by the neighboring relationshipsVis a complete graph...

    Baochun Liet al. Random Network Coding in Peer-to-Peer Networks: From Theory to Practic...

    • ...However, randomized algorithms are often known to be best-effort: even with coding allowed, communicating with random neighbors is only shown to be order-optimal [6]...
    • ...In this paper, unlike most previous works [1]‐[6], [8] that assume node uplinks are the only bottlenecks, we consider both node uplink and downlink capacity constraints...
    • ...Similar to P2P topology models in existing literature [1]‐[6], [8], [9], we assume that a node is able to establish an overlay connection with any other node, so that G forms a full mesh...
    • ...Note that unlike previous works [1]‐[6], [8], [9] that assume the download capacity of each node is unbounded, in this paper, we consider both node upload and download bandwidth constraints...
    • ...Under such a packetized workload, it is reasonable to assume that time is measured in slots [6]‐[10], the length of each slot being the time it takes a node to upload one block at the unit rate...
    • ...Randomized gossip [6], [8] provides an alternative solution with unique benefits over tree-based algorithms...
    • ...For network coding, it is shown in [6] that if each node holds one of the k blocks at the beginning, and in each time slot each node transmits a coded block to a random receiver using network coding, the download finish time of the last node is ck + O( p klog(k)log(N)), where c is a...
    • ...Different from previous works [1]‐[6], [8], [9] that assume unbounded node download capacities, in this paper, we consider the general and more practical case with both node upload and download bandwidth constraints...
    • ...First, as compared to [6] that shows network coding based gossip is order-optimal in homogeneous networks with unbounded download capacity, Theorem 1 proves that if coding is allowed, simple randomized receiver selection can be absolutely optimal as k scales, even if both node upload and download capacities are constrained...
    • ...While most prior work [4], [6], [8] focuses on homogeneous networks, Theorem 2 shows that for heterogeneous networks, with network coding, even simple randomized rate allocation independent of node buffer states can achieve fair and approximately optimal rates for sufficiently large N. In other words, node i finishes downloading all k blocks at time Ti(k) k/Ui as k scales...

    Di Niuet al. Asymptotic optimality of randomized peer-to-peer broadcast with networ...

    • ...Since the exact characterization of network coding in gossiping systems is extremely difficult if not impossible as shown in [4], [5], we trade the accuracy of analysis for the cleanness of the results...
    • ...Deb et al. [4] show in a timeslotted model that network coding can achieve a shorter broadcast delay of k blocks in complete graphs, as compared to a sequential dissemination...

    Di Niuet al. Analyzing the Resilience-Complexity Tradeoff of Network Coding in Dyna...

    • ...This large gap can be closed if we take advantage of random linear coding where a random combination of all messages are transmitted instead of a specific message [12], or twosided protocols which always disseminates innovative message if possible [13]...
    • ...Orderwise optimal spreading time can be achieved in either complete graphs [12] or geometric graphs with constant maximum degree [14]...
    • ...(As an aside, we note that the poly-logarithmic gap from optimality cannot be closed with push-only random gossip even for complete graphs [12], [13])...

    Yuxin Chenet al. Sharing multiple messages over mobile networks

    • ...P2P protocols based on fountain codes have been considered in [14], [15], and random linear network coding has been employed in P2P technology in [16]-[19]...
    • ...diversity of packets in the network than simple routing and forwarding and has been implemented in peer-to-peer networks [16], [29]...

    Ebad Ahmedet al. Optimal Delay-Reconstruction Tradeoffs in Peer-to-Peer Networks

Sort by: