×

Gossip Latin square and the meet-all gossipers problem. (English) Zbl 1330.90092

Summary: Given a network of \(n=2^k\) gossipers, we want to schedule a cyclic calendar of meetings between all of them, such that: (1) each gossiper meets (gossips) only once a day, with one other gossiper, (2) in every \((n-1)\) consecutive days, each gossiper meets all other gossipers, and (3) every gossip, initiated by any gossiper, will reach all gossipers within \(k=\log (n)\) days.
In this paper we study the above stated meet-all gossipers problem, by defining and constructing the Gossip Latin Square (GLS), a combinatorial structure which solves the problem. We then present an efficient construction of GLS, based on maximal Fibonacci LFSR.

MSC:

90C27 Combinatorial optimization
05B15 Orthogonal arrays, Latin squares, Room squares
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bhuyan, L. N.; Agrawal, D. P., Generalized hypercube and hyperbus structures for a computer network, IEEE Trans. Comput., 323-333 (1984) · Zbl 0528.68002
[2] Grigni, Michelangelo; Peleg, David, Tight bounds on mimimum broadcast networks, SIAM J. Discrete Math., 4, 2, 207-222 (1991) · Zbl 0725.94016
[3] Hedetniemi, Sandra M.; Hedetniemi, Stephen T.; Liestman, Arthur L., A survey of gossiping and broadcasting in communication networks, Networks, 18, 4, 319-349 (1988) · Zbl 0649.90047
[4] Kempe, David; Kleinberg, Jon, Protocols and impossibility results for gossip-based communication mechanisms, (Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002 (2002), IEEE), 471-480
[5] Klein, Andreas, Linear feedback shift registers, (Stream Ciphers (2013), Springer), 17-58
[6] Kleitman, D. J.; Shearer, J. B., Further gossip problems, Discrete Math., 30, 2, 151-156 (1980) · Zbl 0444.05015
[7] Laywine, Charles F.; Mullen, Gary L., Discrete Mathematics Using Latin Squares (1998), Wiley: Wiley New York · Zbl 0957.05002
[8] Pfitzmann, A.; Hansen, M., A terminology for talking about privacy by data minimization: anonymity, unlinkability, undetectability, unobservability, pseudonymity, and identity management (2010)
[9] Saad, Youcef; Schultz, Martin H., Topological properties of hypercubes, IEEE Trans. Comput., 37, 7, 867-872 (1988)
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.