×

Dynamic gossip. (English) Zbl 1421.68004

Summary: A gossip protocol is a procedure for spreading secrets among a group of agents, using a connection graph. The goal is for all agents to get to know all secrets, in which case we call the execution of the protocol successful. We consider distributed and dynamic gossip protocols. In distributed gossip, the agents themselves instead of a global scheduler determine whom to call. In dynamic gossip, not only secrets are exchanged but also telephone numbers (agent identities). This results in increased graph connectivity. We define six such distributed dynamic gossip protocols, and we characterize them in terms of the topology of the graphs on which they are successful, wherein we distinguish strong success (the protocol always terminates, possibly assuming fair scheduling) from weak success (the protocol sometimes terminates). For five of these protocols, strong success (fair) and weak success are characterized by weakly connected graphs. This result is surprising, because the protocols are fairly different. In the sixth protocol, an agent may only call another agent if it does not know the other agent’s secret. Strong success for this protocol is characterized by graphs for which the set of non-terminal nodes is strongly connected. Weak success for this protocol is characterized by weakly connected graphs satisfying further topological constraints that we define in the paper. One direction of this characterization is surprisingly harder to prove than the other results in this contribution.

MSC:

68M12 Network protocols
68M14 Distributed systems
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Apt, K., Grossi, D., van der Hoek, W.: Epistemic protocols for distributed gossiping. In: Ramanujam, R. (ed.) Proceedings of 15th TARK (2015), pp. 51-66. https://doi.org/10.4204/EPTCS.215.5 · Zbl 1483.68361
[2] Attamah, M., van Ditmarsch, H., Grossi, D., van der Hoek, W.: Knowledge and gossip. In: Proceedings of 21st ECAI, pp. 21-26. IOS Press, Amsterdam (2014) · Zbl 1366.68007
[3] Attamah, M.; Ditmarsch, H.; Grossi, D.; Hoek, W.; Başkent, C. (ed.); Moss, L. (ed.); Ramanujam, R. (ed.), The pleasure of gossip, 145-163 (2017), Berlin · Zbl 1437.03056 · doi:10.1007/978-3-319-47843-2_9
[4] Baker, B., Shostak, R.: Gossips and telephones. Discrete Math. 2(3), 191-193 (1972) · Zbl 0245.05002 · doi:10.1016/0012-365X(72)90001-5
[5] Boyd, D.W., Steele, J.M.: Random exchanges of information. J. Appl. Probab. 16(3), 657-661 (1979) · Zbl 0422.60078 · doi:10.2307/3213094
[6] Bumby, R.: A problem with telephones. SIAM J. Algebraic Discrete Methods 2(1), 13-18 (1981) · Zbl 0499.05034 · doi:10.1137/0602002
[7] Doerr, B., Friedrich, T., Sauerwald, T.: Quasirandom rumor spreading. ACM Trans. Algorithms 11(2), 1-35 (2014) · Zbl 1398.68055 · doi:10.1145/2650185
[8] Eugster, P.T., Guerraoui, R., Kermarrec, A., Massoulié, L.: Epidemic information dissemination in distributed systems. IEEE Comput. 37(5), 60-67 (2004) · doi:10.1109/MC.2004.1297243
[9] Golumbic, M.C.: The general gossip problem. Technical Report IBM Research Report RC4977, IBM (1974)
[10] Haeupler, B.: Simple, fast and deterministic gossip and rumor spreading. J. ACM 62(6), 47 (2015) · Zbl 1421.68131 · doi:10.1145/2767126
[11] Haeupler, B., Pandurangan, G., Peleg, D., Rajaraman, R., Sun, Z.: Discovery through gossip. Random Struct. Algorithms 48(3), 565-587 (2016) · Zbl 1338.05253 · doi:10.1002/rsa.20621
[12] Haigh, J.: Random exchanges of information. J. Appl. Probab. 18(3), 743-746 (1981) · Zbl 0467.60013 · doi:10.2307/3213330
[13] Hajnal, A., Milner, E.C., Szemeredi, E.: A cure for the telephone problem. Can. Math. Bull. 15(3), 447-450 (1972) · Zbl 0251.05132 · doi:10.4153/CMB-1972-081-0
[14] Harary, F., Schwenk, A.J.: The communication problem on graphs and digraphs. J. Frankl. Inst. 297, 491-495 (1974) · Zbl 0307.05118 · doi:10.1016/0016-0032(74)90126-4
[15] Harchol-Balter, M., Leighton, F.T., Lewin, D.: Resource discovery in distributed networks. In: Proceedings of 8th PODC, pp. 229-237. ACM, New York (1999). https://doi.org/10.1145/301308.301362 · Zbl 1321.68083
[16] Hedetniemi, S., Hedetniemi, S., Liestman, A.: A survey of gossiping and broadcasting in communication networks. Networks 18, 319-349 (1988) · Zbl 0649.90047 · doi:10.1002/net.3230180406
[17] Hromkovic, J., Klasing, R., Pelc, A., Ruzicka, P., Unger, W.: Dissemination of Information in Communication Networks: Broadcasting, Gossiping, Leader Election, and Fault-Tolerance. Springer, Berlin (2005) · Zbl 1067.68016
[18] Hurkens, C.: Spreading gossip efficiently. Nieuw Archief voor Wiskunde 5(1), 208-210 (2000)
[19] Kermarrec, A.-M., van Steen, M.: Gossiping in distributed systems. SIGOPS Oper. Syst. Rev. 41(5), 2-7 (2007) · doi:10.1145/1317379.1317381
[20] Knödel, W.: New gossips and telephones. Discrete Math. 13, 95 (1975) · Zbl 0305.05001 · doi:10.1016/0012-365X(75)90090-4
[21] Moon, J.: Random exchanges of information. Nieuw Archief voor Wiskunde 3(20), 246-249 (1972) · Zbl 0246.60069
[22] Tijdeman, R.: On a telephone problem. Nieuw Archief voor Wiskunde 3(19), 188-192 (1971) · Zbl 0226.05001
[23] van Ditmarsch, H., Kokkinis, I., Stockmarr, A.: Reachability and expectation in gossiping. In: Proceedings of the 20th PRIMA. LNCS, vol. 10621, pp. 93-109. Springer, Berlin (2017) · Zbl 1498.68344
[24] van Ditmarsch, H., van Eijck, J., Pardo, P., Ramezanian, R., Schwarzentruber, F.: Epistemic protocols for dynamic gossip. J. Appl. Log. 20, 1-31 (2017) · Zbl 1401.68017 · doi:10.1016/j.jal.2016.12.001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.