泛洪算法过程的终端

作者：Walter Hussak,Amitabh Trehan

摘要：泛洪是所有分布式网络算法中最简单和最基本的算法之一。节点通过向其所有相邻节点发送消息来开始该过程，在下一轮中将消息转发给他们未从其接收消息的所有相邻节点，依此类推。我们假设节点没有记录泛洪事件。我们称之为记忆性泛滥（AF）。由于节点忘记了，如果在后续轮次中再次接收到消息，则将再次转发该消息，从而提高了消息即使在有限图上也可以无限循环的可能性。据我们所知，这种洪水过程终止的问题尚未解决 - 相反，隐含地假设不终止。

在本文中，我们表明同步AF总是终止于任意有限图，并导出精确的终止时间，这些终止时间在二分图和非二分图中急剧不同。设G是有限连通图。我们证明来自单个源节点的同步AF终止于G轮中的G，其中e是源节点的偏心率，当且仅当G是二分的时候。对于非二分G，来自单个源的同步AF终止于j轮，其中e <j≤e+ d + 1且d是G的直径。这将终止时间限制为最多d和最多2d + 1的二分分别为非二分图和非二分图。如果向所有节点进行通信/广播是动机，我们的结果表明AF渐近时间最优，并且不需要构建和维护跨越树等跨越结构。二分图和非二分图的终止时间的明确分离也表明了在任意图中分布式发现拓扑/距离的机制。

泛洪是所有分布式网络算法中最简单和最基本的算法之一。节点通过向其所有邻居和邻居发送消息来开始该过程，在下一轮中将消息转发给他们未从其接收消息的所有邻居，依此类推。我们假设节点没有记录泛洪事件。我们称之为记忆性泛滥（AF）。由于节点忘记了，如果在后续轮次中再次接收到消息，则将再次转发该消息，从而提高了消息即使在有限图上也可以无限循环的可能性。据我们所知，这种洪水过程终止的问题尚未解决 - 相反，隐含地假设不终止。

在本文中，我们表明同步AF总是终止于任意有限图，并导出精确的终止时间，这些终止时间在二分图和非二分图中不同。设G是有限连通图。我们证明来自单个源节点的同步AF终止于G轮中的G，其中e是源节点的偏心率，当且仅当G是二分的时候。对于非二分G，来自单个源的同步AF终止于j轮，其中e <j≤e+ d + 1且d是G的直径。这将终止时间限制为最多d和最多2d + 1的二分分别为非二分图和非二分图。如果向所有节点进行通信/广播是动机，我们的结果表明AF渐近时间最优，并且不需要构建和维护跨越树等跨越结构。二分图和非二分图的终止时间的明确分离也表明了在任意图中分布式发现拓扑/距离的机制。

为了比较，我们表明在异步网络中，自适应对手可以强制AF不终止。

原文标题：On The Termination of a Flooding Process

原文摘要：Flooding is among the simplest and most fundamental of all distributed network algorithms. A node begins the process by sending a message to all its neighbours and the neighbours, in the next round forward the message to all the neighbours they did not receive the message from and so on. We assume that the nodes do not keep a record of the flooding event. We call this amnesiac flooding (AF). Since the node forgets, if the message is received again in subsequent rounds, it will be forwarded again raising the possibility that the message may be circulated infinitely even on a finite graph. As far as we know, the question of termination for such a flooding process has not been settled - rather, non-termination is implicitly assumed.

In this paper, we show that synchronous AF always terminates on any arbitrary finite graph and derive exact termination times which differ sharply in bipartite and non-bipartite graphs. LetGbe a finite connected graph. We show that synchronous AF from a single source node terminates onGinerounds, whereeis the eccentricity of the source node, if and only ifGis bipartite. For non-bipartiteG, synchronous AF from a single source terminates injrounds wheree<j≤e+d+1anddis the diameter ofG. This limits termination time to at mostdand at most2d+1for bipartite and non-bipartite graphs respectively. If communication/broadcast to all nodes is the motivation, our results show that AF is asymptotically time optimal and obviates the need for construction and maintenance of spanning structures like spanning trees. The clear separation in the termination times of bipartite and non-bipartite graphs also suggests mechanisms for distributed discovery of the topology/distances in arbitrary graphs.

For comparison, we show that, in asynchronous networks, an adaptive adversary can force AF to be non-terminating.

地址：https://arxiv.org/abs/1907.07078