{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T17:55:26Z","timestamp":1725558926130},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642141614"},{"type":"electronic","value":"9783642141621"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-14162-1_10","type":"book-chapter","created":{"date-parts":[[2010,7,5]],"date-time":"2010-07-05T05:26:21Z","timestamp":1278307581000},"page":"115-126","source":"Crossref","is-referenced-by-count":6,"title":["How Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange)"],"prefix":"10.1007","author":[{"given":"Dan","family":"Alistarh","sequence":"first","affiliation":[]},{"given":"Seth","family":"Gilbert","sequence":"additional","affiliation":[]},{"given":"Rachid","family":"Guerraoui","sequence":"additional","affiliation":[]},{"given":"Morteza","family":"Zadimoghaddam","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","unstructured":"Karp, R., Schindelhauer, C., Shenker, S., V\u00f6cking, B.: Randomized rumor spreading. In: FOCS (2000)"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Demers, A., Greene, D., Hauser, C., Irish, W., Larson, J., Shenker, S., Sturgis, H., Swinehart, D., Terry, D.: Epidemic algorithms for replicated database maintenance. In: PODC (1987)","DOI":"10.1145\/41840.41841"},{"key":"10_CR3","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1145\/312203.312207","volume":"17","author":"K. Birman","year":"1999","unstructured":"Birman, K., Hayden, M., Ozkasap, O., Xiao, Z., Budiu, M., Minsky, Y.: Bimodal multicast. ACM Trans. on Comp. Sys.\u00a017, 41\u201386 (1999)","journal-title":"ACM Trans. on Comp. Sys."},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Eugster, P., Guerraoui, R., Handurukande, S., Kermarrec, A.-M., Kouznetsov, P.: Lightweight probabilistic broadcast. ACM Trans. on Comp. Sys.\u00a021(4) (2003)","DOI":"10.1145\/945506.945507"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Kermarrec, A., Massoulie, L., Ganesh, A.: Probabilistic reliable multicast in ad hoc networks. IEEE Trans. on Parallel and Distr. Syst.\u00a014 (2003)","DOI":"10.1109\/TPDS.2003.1189583"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Demers, A.: Spatial gossip and resource location protocols. Journal of ACM, 943\u2013967 (2004)","DOI":"10.1145\/1039488.1039491"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Chaintreau, A., Le Boudec, J.-Y., Ristanovic, N.: The age of gossip: spatial mean field regime. In: SIGMETRICS (2009)","DOI":"10.1145\/1555349.1555363"},{"issue":"8","key":"10_CR8","doi-asserted-by":"publisher","first-page":"1262","DOI":"10.1016\/j.jcss.2006.08.001","volume":"72","author":"B.S. Chlebus","year":"2006","unstructured":"Chlebus, B.S., Kowalski, D.R.: Robust gossiping with an application to consensus. J. Comput. Syst. Sci.\u00a072(8), 1262\u20131281 (2006)","journal-title":"J. Comput. Syst. Sci."},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Chlebus, B.S., Kowalski, D.R.: Time and communication efficient consensus for crash failures (2006)","DOI":"10.1007\/11864219_22"},{"key":"10_CR10","doi-asserted-by":"crossref","unstructured":"Frieze, A.M., Grimmett, G.: The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics\u00a0(10), 55\u201377 (1985)","DOI":"10.1016\/0166-218X(85)90059-9"},{"issue":"1","key":"10_CR11","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1137\/0147013","volume":"47","author":"B. Pittel","year":"1987","unstructured":"Pittel, B.: On spreading a rumor. SIAM J. Appl. Math.\u00a047(1), 213\u2013223 (1987)","journal-title":"SIAM J. Appl. Math."},{"key":"10_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1007\/3-540-52921-7_62","volume-title":"Algorithms","author":"U. Feige","year":"1990","unstructured":"Feige, U., Peleg, D., Raghavan, P., Upfal, E.: Randomized broadcast in networks. In: Asano, T., Imai, H., Ibaraki, T., Nishizeki, T. (eds.) SIGAL 1990. LNCS, vol.\u00a0450, pp. 128\u2013137. Springer, Heidelberg (1990)"},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Els\u00e4sser, R.: On the communication complexity of randomized broadcasting in random-like graphs. In: SPAA (2006)","DOI":"10.1145\/1148109.1148135"},{"key":"10_CR14","doi-asserted-by":"crossref","unstructured":"Berenbrink, P., Elsaesser, R., Friedetzky, T.: Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems. In: PODC (2008)","DOI":"10.1145\/1400751.1400773"},{"key":"10_CR15","unstructured":"Els\u00e4sser, R., Sauerwald, T.: The power of memory in randomized broadcasting. In: SODA (2008)"},{"issue":"36","key":"10_CR16","doi-asserted-by":"publisher","first-page":"3414","DOI":"10.1016\/j.tcs.2008.04.017","volume":"410","author":"R. Els\u00e4sser","year":"2009","unstructured":"Els\u00e4sser, R., Sauerwald, T.: On the runtime and robustness of randomized broadcasting. Theor. Comput. Sci.\u00a0410(36), 3414\u20133427 (2009)","journal-title":"Theor. Comput. Sci."},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"Doerr, B., Friedrich, T., Sauerwald, T.: Quasirandom rumor spreading. In: SODA (2008)","DOI":"10.1016\/j.endm.2009.07.040"},{"key":"10_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1007\/978-3-642-02927-1_31","volume-title":"Automata, Languages and Programming","author":"B. Doerr","year":"2009","unstructured":"Doerr, B., Friedrich, T., Sauerwald, T.: Quasirandom rumor spreading: Expanders, push vs. pull, and robustness. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05555, pp. 366\u2013377. Springer, Heidelberg (2009)"},{"key":"10_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_82","volume-title":"Algorithms and Computation","author":"B. Doerr","year":"2009","unstructured":"Doerr, B., Huber, A., Levavi, A.: Strong robustness of randomized rumor spreading protocols. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878. Springer, Heidelberg (2009)"},{"key":"10_CR20","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1137\/S0895480295292934","volume":"11","author":"A. Czumaj","year":"1998","unstructured":"Czumaj, A., Gasieniec, L., Pelc, A.: Time and cost trade-offs in gossiping. SIAM Journal on Discrete Mathematics\u00a011, 400\u2013413 (1998)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Georgiou, C., Gilbert, S., Guerraoui, R., Kowalski, D.R.: On the complexity of asynchronous gossip. In: PODC (2008)","DOI":"10.1145\/1400751.1400771"},{"key":"10_CR22","volume-title":"Dissemination of information in Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance","author":"J. Hromkovic","year":"2005","unstructured":"Hromkovic, J., Klasing, R., Pelc, A., Ruzika, P., Unger, W.: Dissemination of information in Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance. Springer, Heidelberg (2005)"},{"key":"10_CR23","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Pavlov, E., Vaikuntanathan, V.: Byzantine agreement in the full-information model in O(log n) rounds. In: STOC (2006)","DOI":"10.1145\/1132516.1132543"},{"key":"10_CR24","unstructured":"Kapron, B.M., Kempe, D., King, V., Saia, J., Sanwalani, V.: Fast asynchronous byzantine agreement and leader election with full information. In: SODA, pp. 1038\u20131047 (2008)"},{"key":"10_CR25","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J., Sanwalani, V., Vee, E.: Scalable leader election. In: SODA, pp. 990\u2013999 (2006)","DOI":"10.1145\/1109557.1109667"},{"key":"10_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04355-0_47","volume-title":"Distributed Computing","author":"V. King","year":"2009","unstructured":"King, V., Saia, J.: Fast, scalable byzantine agreement in the full information model with a nonadaptive adversary. In: Keidar, I. (ed.) DISC 2009. LNCS, vol.\u00a05805. Springer, Heidelberg (2009)"},{"key":"10_CR27","doi-asserted-by":"crossref","unstructured":"Gilbert, S., Kowalski, D.: Distributed agreement with optimal communication complexity. In: SODA (2010)","DOI":"10.1137\/1.9781611973075.78"},{"key":"10_CR28","unstructured":"Alistarh, D., Gilbert, S., Guerraoui, R., Zadimoghaddam, M.: How efficient can gossip be? (technical report), https:\/\/infoscience.epfl.ch\/record\/148544"},{"key":"10_CR29","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1002\/(SICI)1098-2418(199809)13:2<99::AID-RSA1>3.0.CO;2-M","volume":"13","author":"D. Dubhashi","year":"1996","unstructured":"Dubhashi, D., Ranjan, D.: Balls and bins: A study in negative dependence. Random Structures and Algorithms\u00a013, 99\u2013124 (1996)","journal-title":"Random Structures and Algorithms"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-14162-1_10.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,23]],"date-time":"2020-11-23T21:48:04Z","timestamp":1606168084000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-14162-1_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642141614","9783642141621"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-14162-1_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2010]]}}}