{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,4]],"date-time":"2024-05-04T01:43:52Z","timestamp":1714787032819},"reference-count":21,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2012,12,27]],"date-time":"2012-12-27T00:00:00Z","timestamp":1356566400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[2014,9]]},"abstract":"<jats:title>ABSTRACT<\/jats:title><jats:p>We study the stopping times of gossip algorithms for network coding. We analyze algebraic gossip (i.e., random linear coding) and consider three gossip algorithms for information spreading: Pull, Push, and Exchange. The stopping time of algebraic gossip is known to be linear for the complete graph, but the question of determining a tight upper bound or lower bounds for general graphs is still open. We take a major step in solving this question, and prove that algebraic gossip on any graph of size<jats:italic>n<\/jats:italic>is<jats:italic>O<\/jats:italic>(\u0394<jats:italic>n<\/jats:italic>) where \u0394 is the maximum degree of the graph. This leads to a tight bound of<jats:inline-graphic xmlns:xlink=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20480-math-0001.gif\" xlink:title=\"urn:x-wiley:10429832:media:rsa20480:rsa20480-math-0001\"\/>for bounded degree graphs and an upper bound of<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic><jats:sup>2<\/jats:sup>) for general graphs. We show that the latter bound is tight by providing an example of a graph with a stopping time of<jats:inline-graphic xmlns:xlink=\"https:\/\/2.zoppoz.workers.dev:443\/http\/www.w3.org\/1999\/xlink\" xlink:href=\"graphic\/rsa20480-math-0002.gif\" xlink:title=\"urn:x-wiley:10429832:media:rsa20480:rsa20480-math-0002\"\/>. Our proofs use a novel method that relies on Jackson's queuing theorem to analyze the stopping time of network coding; this technique is likely to become useful for future research. \u00a9 2012 Wiley Periodicals, Inc. Random Struct. Alg., 45, 185\u2013217, 2014<\/jats:p>","DOI":"10.1002\/rsa.20480","type":"journal-article","created":{"date-parts":[[2012,12,27]],"date-time":"2012-12-27T07:49:23Z","timestamp":1356594563000},"page":"185-217","source":"Crossref","is-referenced-by-count":1,"title":["Bounds for algebraic gossip on graphs"],"prefix":"10.1002","volume":"45","author":[{"given":"Michael","family":"Borokhovich","sequence":"first","affiliation":[{"name":"Department of Communication Systems Engineering Ben\u2010Gurion University of the Negev Beersheba Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chen","family":"Avin","sequence":"additional","affiliation":[{"name":"Department of Communication Systems Engineering Ben\u2010Gurion University of the Negev Beersheba Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zvi","family":"Lotker","sequence":"additional","affiliation":[{"name":"Department of Communication Systems Engineering Ben\u2010Gurion University of the Negev Beersheba Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2012,12,27]]},"reference":[{"key":"e_1_2_9_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993883"},{"key":"e_1_2_9_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2010.5513272"},{"key":"e_1_2_9_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874516"},{"key":"e_1_2_9_5_1","first-page":"1653","volume-title":"INFOCOM","author":"Boyd S. P.","year":"2005"},{"key":"e_1_2_9_6_1","volume-title":"vol. 46 of Applications of Mathematics","author":"Chen H.","year":"2001"},{"key":"e_1_2_9_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.874532"},{"key":"e_1_2_9_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1111322.1111337"},{"key":"e_1_2_9_9_1","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198572237.001.0001","volume-title":"Probability and random processes","author":"Grimmett G. R.","year":"2001"},{"key":"e_1_2_9_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993676"},{"key":"e_1_2_9_11_1","first-page":"442","volume-title":"ISIT","author":"Ho T.","year":"2003"},{"key":"e_1_2_9_12_1","doi-asserted-by":"crossref","volume-title":"Random graphs and complex networks","author":"Hofstad R. V. D.","DOI":"10.1017\/9781316779422"},{"key":"e_1_2_9_13_1","first-page":"565","volume-title":"FOCS","author":"Karp R. M.","year":"2000"},{"key":"e_1_2_9_14_1","first-page":"482","volume-title":"FOCS","author":"Kempe D.","year":"2003"},{"key":"e_1_2_9_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.807285"},{"key":"e_1_2_9_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.phycom.2008.01.006"},{"key":"e_1_2_9_17_1","first-page":"122","volume-title":"INFOCOM","author":"M\u00e9dard M.","year":"2002"},{"key":"e_1_2_9_18_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813603"},{"key":"e_1_2_9_19_1","first-page":"1748","volume-title":"ISIT","author":"Mosk\u2010Aoyama D.","year":"2006"},{"key":"e_1_2_9_20_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_9_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/9780470994672"},{"key":"e_1_2_9_22_1","volume-title":"Algebraic gossip on arbitrary networks","author":"Vasudevan D.","year":"2009"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20480","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.20480","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.20480","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,4]],"date-time":"2024-05-04T00:57:49Z","timestamp":1714784269000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.20480"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,27]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,9]]}},"alternative-id":["10.1002\/rsa.20480"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1002\/rsa.20480","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12,27]]}}}