Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(5)
Communication Model
Discrete Time
Linear Code
Natural Extension
Network Coding
Related Publications
(11)
Correctness of a gossip based membership protocol
Avalanche: A Network Coding Analysis
NegotiationBased Protocols for Disseminating Information in Wireless Sensor Networks
Information Dissemination via Network Coding
Randomized rumor spreading
Subscribe
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
Edit
Algebraic gossip: a network coding approach to optimal multiple rumor mongering
(
Citations: 81
)
BibTex

RIS

RefWorks
Download
Supratim Deb
,
Muriel Médard
,
Clifford Choute
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 discretetime steps, and in every timestep, 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 timestep, 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 gossipbased 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. 24862507, 2006
DOI:
10.1145/1148663.1148678
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.
(
ieeexplore.ieee.org
)
(
www.mit.edu
)
(
www.mit.edu
)
(
web.mit.edu
)
(
www.informatik.unitrier.de
)
(
www.mit.edu
)
(
doi.acm.org
)
(
www.mit.edu
)
More »
Citation Context
(48)
...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 Li
,
et al.
Random Network Coding in PeertoPeer Networks: From Theory to Practic...
...However, randomized algorithms are often known to be besteffort: even with coding allowed, communicating with random neighbors is only shown to be orderoptimal [
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 treebased 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 orderoptimal 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 Niu
,
et al.
Asymptotic optimality of randomized peertopeer 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 Niu
,
et al.
Analyzing the ResilienceComplexity 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 polylogarithmic gap from optimality cannot be closed with pushonly random gossip even for complete graphs [
12
], [13])...
Yuxin Chen
,
et 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 peertopeer networks [
16
], [29]...
Ebad Ahmed
,
et al.
Optimal DelayReconstruction Tradeoffs in PeertoPeer Networks
References
(17)
Network information flow
(
Citations: 2583
)
Rudolf Ahlswede
,
Ning Cai
,
Shuoyen Robert Li
,
Raymond W. Yeung
Journal:
IEEE Transactions on Information Theory  TIT
, vol. 46, no. 4, pp. 12041216, 2000
Epidemic algorithms for replicated database maintenance
(
Citations: 845
)
Alan J. Demers
,
Daniel H. Greene
,
Carl Hauser
,
Wes Irish
,
John Larson
,
Scott J. Shenker
,
Howard E. Sturgis
,
Daniel C. Swinehart
,
Douglas B. Terry
Conference:
Symposium on Principles of Distributed Computing  PODC
, pp. 112, 1987
Low complexity algebraic network codes
(
Citations: 17
)
S. Jaggi
,
P. A. Chou
,
K. Jain
Published in 2003.
Randomized rumor spreading
(
Citations: 254
)
Richard M. Karp
,
Christian Schindelhauer
,
Scott Shenker
,
B. Vocking
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 565574, 2000
Protocols and Impossibility Results for GossipBased Communication Mechanisms
(
Citations: 54
)
David Kempe
,
Jon M. Kleinberg
Conference:
IEEE Symposium on Foundations of Computer Science  FOCS
, pp. 471480, 2002
Sort by:
Citations
(81)
Random Network Coding in PeertoPeer Networks: From Theory to Practice
(
Citations: 2
)
Baochun Li
,
Di Niu
Journal:
Proceedings of The IEEE  PIEEE
, vol. 99, no. 3, pp. 513523, 2011
Asymptotic optimality of randomized peertopeer broadcast with network coding
(
Citations: 1
)
Di Niu
,
Baochun Li
Conference:
IEEE INFOCOM  INFOCOM
, pp. 11971205, 2011
Meanfield framework for performance evaluation of pushpull gossip protocols
(
Citations: 2
)
Rena Bakhshi
,
Lucia Cloth
,
Wan Fokkink
,
Boudewijn R. Haverkort
Journal:
Performance Evaluation  PE
, vol. 68, no. 2, pp. 157179, 2011
Analyzing the ResilienceComplexity Tradeoff of Network Coding in Dynamic P2P Networks
(
Citations: 1
)
Di Niu
,
Baochun Li
Journal:
IEEE Transactions on Parallel and Distributed Systems  TPDS
, vol. 22, no. 11, pp. 18421850, 2011
Sharing multiple messages over mobile networks
(
Citations: 1
)
Yuxin Chen
,
Sanjay Shakkottai
,
Jeffrey G. Andrews
Conference:
IEEE INFOCOM  INFOCOM
, pp. 658666, 2011