Broadcast in the rendezvous model

详细信息    查看全文

• 作者：Philippe Duchon ; Nicolas Hanusse ; Nasser Saheb and Akka Zemmari
• 关键词：Algorithms and data structures ; Distributed algorithms ; Graph ; Broadcast ; Rendezvous model
• 刊名：Information and Computation
• 出版年：2006
• 出版时间：May 2006
• 年：2006
• 卷：204
• 期：5
• 页码：697-712
• 全文大小：182 K

文摘

In many large, distributed or mobile networks, broadcast algorithms are used to update information stored at the nodes. In this paper, we propose a new model of communication based on rendezvous and analyze a multi-hop distributed algorithm to broadcast a message in a synchronous setting. In the rendezvous model, two neighbors u and v can communicate if and only if u calls v and v calls u simultaneously. Thus nodes u and v obtain a rendezvous at a meeting point. If m is the number of meeting points, the network can be modeled by a graph of n vertices and m edges. At each round, every vertex chooses a random neighbor and there is a rendezvous if an edge has been chosen by its two extremities. Rendezvous enable an exchange of information between the two entities. We get sharp lower and upper bounds on the time complexity in terms of number of rounds to broadcast: we show that, for any graph, the expected number of rounds is between ln n and O (n²). For these two bounds, we prove that there exist some graphs for which the expected number of rounds is either O (ln (n)) or Ω (n²). For specific topologies, additional bounds are given.