Network Coding Based Information Spreading in Dynamic Networks With Correlated Data
In this paper, we design and analyze information spreading algorithms for dynamic networks with correlated data. In these networks, either the data to be distributed, the data already available at the nodes, or both are correlated. Moreover, nodes' availability and connectivity is dynamic - a s...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2016
|
| Online Access: | http://hdl.handle.net/1721.1/100956 https://orcid.org/0000-0003-4059-407X |
| _version_ | 1826195917413285888 |
|---|---|
| author | Cohen, Asaf Haeupler, Bernhard Avin, Chen Medard, Muriel |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Cohen, Asaf Haeupler, Bernhard Avin, Chen Medard, Muriel |
| author_sort | Cohen, Asaf |
| collection | MIT |
| description | In this paper, we design and analyze information spreading algorithms for dynamic networks with correlated data. In these networks, either the data to be distributed, the data already available at the nodes, or both are correlated. Moreover, nodes' availability and connectivity is dynamic - a scenario typical for wireless networks. Our contribution is twofold. First, although coding schemes for correlated data have been studied extensively, the focus has been on characterizing the rate region in static networks. In an information spreading scheme, however, nodes may communicate by continuously exchanging packets according to some underlying communication model. The main figure of merit is the stopping time - the time required until nodes can successfully decode. While information spreading schemes, such as gossip, are practical, distributed, and scalable, they have only been studied for uncorrelated data. We close this gap by providing techniques to analyze network-coded information spreading in dynamic networks with correlated data. Second, we give a clean framework for oblivious dynamic network models that in particular applies to a multitude of wireless network and communication scenarios. We specify a general setting for the data model and give tight bounds on the stopping times of network-coded protocols in this wide range of settings. En route, we analyze the capacities seen by nodes under a network-coded information spreading protocol, a previously unexplored question. We conclude with extensive simulations, clearly validating the key trends and phenomena predicted in the analysis. |
| first_indexed | 2024-09-23T10:17:53Z |
| format | Article |
| id | mit-1721.1/100956 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:17:53Z |
| publishDate | 2016 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1009562022-09-26T17:04:08Z Network Coding Based Information Spreading in Dynamic Networks With Correlated Data Cohen, Asaf Haeupler, Bernhard Avin, Chen Medard, Muriel Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Research Laboratory of Electronics Medard, Muriel In this paper, we design and analyze information spreading algorithms for dynamic networks with correlated data. In these networks, either the data to be distributed, the data already available at the nodes, or both are correlated. Moreover, nodes' availability and connectivity is dynamic - a scenario typical for wireless networks. Our contribution is twofold. First, although coding schemes for correlated data have been studied extensively, the focus has been on characterizing the rate region in static networks. In an information spreading scheme, however, nodes may communicate by continuously exchanging packets according to some underlying communication model. The main figure of merit is the stopping time - the time required until nodes can successfully decode. While information spreading schemes, such as gossip, are practical, distributed, and scalable, they have only been studied for uncorrelated data. We close this gap by providing techniques to analyze network-coded information spreading in dynamic networks with correlated data. Second, we give a clean framework for oblivious dynamic network models that in particular applies to a multitude of wireless network and communication scenarios. We specify a general setting for the data model and give tight bounds on the stopping times of network-coded protocols in this wide range of settings. En route, we analyze the capacities seen by nodes under a network-coded information spreading protocol, a previously unexplored question. We conclude with extensive simulations, clearly validating the key trends and phenomena predicted in the analysis. United States. Defense Advanced Research Projects Agency (Contract N66001-11-C-4003) Office of the Chief Scientist of Israel (RESCUE) 2016-01-20T18:16:15Z 2016-01-20T18:16:15Z 2015-03 2014-11 Article http://purl.org/eprint/type/JournalArticle 0733-8716 http://hdl.handle.net/1721.1/100956 Cohen, Asaf, Bernhard Haeupler, Chen Avin, and Muriel Medard. “Network Coding Based Information Spreading in Dynamic Networks With Correlated Data.” IEEE Journal on Selected Areas in Communications 33, no. 2 (February 2015): 213–224. doi:10.1109/jsac.2014.2384293. https://orcid.org/0000-0003-4059-407X en_US http://dx.doi.org/10.1109/JSAC.2014.2384293 IEEE Journal on Selected Areas in Communications Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) Other univ. web domain |
| spellingShingle | Cohen, Asaf Haeupler, Bernhard Avin, Chen Medard, Muriel Network Coding Based Information Spreading in Dynamic Networks With Correlated Data |
| title | Network Coding Based Information Spreading in Dynamic Networks With Correlated Data |
| title_full | Network Coding Based Information Spreading in Dynamic Networks With Correlated Data |
| title_fullStr | Network Coding Based Information Spreading in Dynamic Networks With Correlated Data |
| title_full_unstemmed | Network Coding Based Information Spreading in Dynamic Networks With Correlated Data |
| title_short | Network Coding Based Information Spreading in Dynamic Networks With Correlated Data |
| title_sort | network coding based information spreading in dynamic networks with correlated data |
| url | http://hdl.handle.net/1721.1/100956 https://orcid.org/0000-0003-4059-407X |
| work_keys_str_mv | AT cohenasaf networkcodingbasedinformationspreadingindynamicnetworkswithcorrelateddata AT haeuplerbernhard networkcodingbasedinformationspreadingindynamicnetworkswithcorrelateddata AT avinchen networkcodingbasedinformationspreadingindynamicnetworkswithcorrelateddata AT medardmuriel networkcodingbasedinformationspreadingindynamicnetworkswithcorrelateddata |