Odd gossiping

详细信息    查看全文

• 作者：Guillaume Fertin^a ; ^{guillaume.fertin@univ-nantes.fr} ; Joseph G. Peters^b ; ^{peters@cs.sfu.ca} ; Lynette Raabe^b ; Charlie Xu^b ; ¹ ; ^{charliex@amazon.com}
• 关键词：Gossiping ; Information dissemination ; Communication networks
• 刊名：Discrete Applied Mathematics
• 出版年：2017
• 出版时间：10 January 2017
• 年：2017
• 卷：216
• 期：part_P3
• 页码：550-561
• 全文大小：561 K
• 卷排序：216

文摘

Gossiping   is an information dissemination process in which each node of a communication network has a piece of information that must be received by all other nodes. Most previous work on this problem has concentrated on networks for which the number of nodes nn is even. We investigate networks for which nn is odd. We use a linear cost model of communication in which the cost of communication is proportional to the amount of information transmitted. We study two variants of the problem. In synchronous gossiping, the pairwise communications are organized into rounds and all communications in a round start at the same time. In asynchronous   gossiping, a pair of nodes can start communicating while communications between other pairs are in progress. We prove lower bounds on the total time to gossip for both synchronous and asynchronous gossiping. The asynchronous lower bound is achievable for some odd values of nn, but we prove that no gossip algorithm for n=2k−1n=2k−1 nodes, k≥3k≥3, can achieve the bound. For synchronous gossiping, we present an optimal algorithm for n=2k−1n=2k−1. We conjecture that our synchronous lower bound is exact for all odd nn.