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.