کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
428496 | 686785 | 2015 | 6 صفحه PDF | دانلود رایگان |
• 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.
Journal: Information Processing Letters - Volume 115, Issue 10, October 2015, Pages 738–743