Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems
Efficient randomised broadcasting in random regular networks with applications in peer-to-peer systems
复制标题
随机常规网络中的高效随机广播及其在对等系统中的应用
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
T. Friedetzky
中科院分区：
文献类型：
--
作者：
P. Berenbrink;Robert Elsässer;T. Friedetzky
我们考虑通过使用Karp等人介绍的随机电话呼叫模型的简单修改在随机d-正则图中进行广播(Proceages of the FOCS‘00,2000)。在电话呼叫模型中，在每个时间步中，每个节点呼叫随机选择的邻居，以建立到该节点的通信信道。然后，可以双向使用通信信道来传输消息。我们证明，如果我们允许每个节点选择四个不同的邻居而不是一个，则有效广播消息所需的每个节点的平均消息传输次数呈指数下降。形式上，我们给出了一个算法，其时间复杂度为$$O(Logn)$$O(Logn)，并且每条消息使用$$O(Nloglogn)$$O(Nloglogn)次传输。相反，对于标准模型，我们证明了在受限地址无关模型中的每个分布式算法在时间$$O(Logn)$$O(Logn)需要$$omega(nlogn{/}logd)$$Ω(nlogn/logd)消息传输。我们的算法有效地处理有限的通信故障，只需要粗略地估计节点的数量，并且对网络大小的有限变化具有健壮性。我们的结果在对等网络和复制数据库中有应用。
We consider broadcasting in random d-regular graphs by using a simple modification of the random phone call model introduced by Karp et al. (Proceedings of the FOCS ’00, 2000). In the phone call model, in every time step, each node calls a randomly chosen neighbour to establish a communication channel to this node. The communication channels can then be used bi-directionally to transmit messages. We show that, if we allow every node to choose four distinct neighbours instead of one, then the average number of message transmissions per node required to broadcast a message efficiently decreases exponentially. Formally, we present an algorithm that has time complexity $$O(log n)$$O(logn) and uses $$O(nlog log n)$$O(nloglogn) transmissions per message. In contrast, we show for the standard model that every distributed algorithm in a restricted address-oblivious model that broadcasts a message in time $$O(log n)$$O(logn) requires $$Omega (n log n{/} log d)$$Ω(nlogn/logd) message transmissions. Our algorithm efficiently handles limited communication failures, only requires rough estimates of the number of nodes, and is robust against limited changes in the size of the network. Our results have applications in peer-to-peer networks and replicated databases.