Gossip Latin square and the meet-all gossipers problem

• We explore how to optimally spread a rumor when all the participants must meet each other.
• We define Gossipers Latin Square (GLS), and prove it solves the problem.
• We present construction for GLS that uses Fibonacci LFSR, and prove its correctness.

Given a network of n=2kn=2k 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)(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)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.