{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:36:06Z","timestamp":1763458566132,"version":"3.45.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,8,22]],"date-time":"2017-08-22T00:00:00Z","timestamp":1503360000000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF1527110"],"award-info":[{"award-number":["CCF1527110"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2016,9]]},"abstract":"<jats:p>\n                    We introduce projection analysis\u2014a new technique to analyze the stopping time of protocols that are based on random linear network coding (RLNC). Projection analysis drastically simplifies, extends, and strengthens previous results on RLNC gossip protocols. We analyze RLNC gossip in a general framework for network and communication models that encompasses and unifies the models used previously in this context. We show, in most settings for the first time, that the RLNC gossip converges with high probability in optimal time. Most stopping times are of the form\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    +\n                    <jats:italic toggle=\"yes\">T<\/jats:italic>\n                    ), where\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    is the number of messages to be distributed and\n                    <jats:italic toggle=\"yes\">T<\/jats:italic>\n                    is the time it takes to disseminate one message. This means RLNC gossip achieves \u201cperfect pipelining.\u201d\n                  <\/jats:p>\n                  <jats:p>\n                    Our analysis directly extends to highly dynamic networks in which the topology can change completely at any time. This remains true, even if the network dynamics are controlled by a fully adaptive adversary that knows the complete network state. Virtually nothing besides simple\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (\n                    <jats:italic toggle=\"yes\">kT<\/jats:italic>\n                    ) sequential flooding protocols was previously known for such a setting.\n                  <\/jats:p>\n                  <jats:p>While RLNC gossip works in this wide variety of networks our analysis remains the same and extremely simple. This contrasts with more complex proofs that were put forward to give less strong results for various special cases.<\/jats:p>","DOI":"10.1145\/2629696","type":"journal-article","created":{"date-parts":[[2016,8,26]],"date-time":"2016-08-26T08:25:39Z","timestamp":1472199939000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Analyzing Network Coding (Gossip) Made Easy"],"prefix":"10.1145","volume":"63","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3381-0459","authenticated-orcid":false,"given":"Bernhard","family":"Haeupler","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology"}]}],"member":"320","published-online":{"date-parts":[[2016,8,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/263661.263680"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.850663"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.132"},{"key":"e_1_2_1_4_1","volume-title":"Distributed Computing Column, 93 (Oct.","author":"Aspnes James","year":"2007","unstructured":"James Aspnes and Eric Ruppert. 2007. An introduction to population protocols. Bulletin of the European Association for Theoretical Computer Science, Distributed Computing Column, 93 (Oct. 2007), 98--117."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_11"},{"volume-title":"Proceedings of the IEEE International Symposium on Information Theory (ISIT). IEEE","author":"Borokhovich M.","key":"e_1_2_1_6_1","unstructured":"M. Borokhovich, C. Avin, and Z. Lotker. 2010. Tight bounds for algebraic gossip on graphs. In Proceedings of the IEEE International Symposium on Information Theory (ISIT). IEEE, Los Alamitos, CA, 1758--1762."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214064"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33651-5_7"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-015-0244-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806745"},{"volume-title":"Proceedings of the Allerton Conference on Communication Control and Computing. 40--49","author":"Chou P. A.","key":"e_1_2_1_11_1","unstructured":"P. A. Chou, Y. Wu, and K. Jain. 2003. Practical network coding. In Proceedings of the Allerton Conference on Communication Control and Computing. 40--49."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/090756053"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the Allerton Conference on Communication, Control, and Computing.","author":"Deb Supratim","year":"2004","unstructured":"Supratim Deb and Muriel M\u00e9dard. 2004. Algebraic gossip: A network coding approach to optimal multiple rumor mongering. In Proceedings of the Allerton Conference on Communication, Control, and Computing."},{"volume-title":"Proceedings of the IEEE International Symposium on Information Theory (ISIT). IEEE","author":"Deb S.","key":"e_1_2_1_14_1","unstructured":"S. Deb, M. M\u00e9dard, and C. Choute. 2005. On random network coding based information dissemination. In Proceedings of the IEEE International Symposium on Information Theory (ISIT). IEEE, Los Alamitos, CA, 278--282."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874532"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/41840.41841"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627869"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240010406"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111322.1111337"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2007.901080"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41527-2_34"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). 57--68","author":"Giakkoupis George","year":"2011","unstructured":"George Giakkoupis. 2011. Tight bounds for rumor spreading in graphs of a given conductance. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS). 57--68."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634133"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43951-7_42"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the International Conference on Computer Communications (INFOCOM)","volume":"4","author":"Gkantsidis C.","unstructured":"C. Gkantsidis and P. R. Rodriguez. 2005. Network coding for large scale content distribution. In Proceedings of the International Conference on Computer Communications (INFOCOM), vol. 4. 2235--2245."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2006.876186"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993676"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/LCOMM.2012.060112.120632"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627817.2627868"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2012.6283992"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993885"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITW.2011.6089559"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33651-5_12"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611489"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2011.6033713"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230180406"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.881746"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796561"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2008.923722"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946317"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039491"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806760"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.807285"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/935747"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146401"},{"volume-title":"Proceedings of the IEEE International Symposium on Information Theory. IEEE, Los Alamitos, 1748--1752","author":"Mosk-Aoyama D.","key":"e_1_2_1_46_1","unstructured":"D. Mosk-Aoyama and D. Shah. 2006b. Information dissemination via network coding. In Proceedings of the IEEE International Symposium on Information Theory. IEEE, Los Alamitos, 1748--1752."},{"key":"e_1_2_1_47_1","unstructured":"D. Vasudevan and S. Kudekar. 2009. Algebraic gossip on Arbitrary Networks. ArXiv:0901.1444 (2009)."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629696","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629696","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629696","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:32:00Z","timestamp":1763458320000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629696"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,8,22]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,9]]}},"alternative-id":["10.1145\/2629696"],"URL":"https:\/\/doi.org\/10.1145\/2629696","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2016,8,22]]},"assertion":[{"value":"2011-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-01-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-08-22","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}