论文标题
终止洪水案件
Terminating cases of flooding
论文作者
论文摘要
基本的同步洪水在回合中进行。给定有限的（网络）图$ g $，一组来源$ i \ subseteq g $在$ i $中的每个节点在第一轮中发出洪水，向其所有邻居发送相同的消息。在随后的每一轮比赛中，节点将消息发送给他们在上一轮中未收到消息的所有邻居。当$ g $中没有节点时，洪水终止会在一轮中发送消息。终止问题尚未解决 - 而不是终止是可能的。 我们表明，洪水在每个有限图上终止。对于单一来源$ g_0 $，如果$ g $是两部分，则洪水终止于$ e $ rounds，而$ j $ rounds则带有$ e <j \ leq e+d+1 $，否则，$ e $和$ d $是$ g_0 $ $ g_0 $和$ g $ g $的偏心。对于与所有节点的通信/广播，这是渐近的时间最佳时间，并且消除了对跨度结构的构建和维护的需求。我们扩展到有多个消息的多个回合发起的动态洪水。节点仅向邻居发送消息的情况，在上一轮中没有从中接收{\ IT任何}消息，而节点向所有邻居发送了一些最高排名的消息，从而未在上一轮中接收{\ IT}消息，两者都终止。如果网络图随着时间的流逝而失去边缘，则所有这些情况也保持不变。非终止案例包括异步洪水，洪水，消息在边缘有固定的延迟，多消息洪水的案例以及网络图随着时间的推移获得边缘的情况。
Basic synchronous flooding proceeds in rounds. Given a finite undirected (network) graph $G$, a set of sources $I \subseteq G$ initiate flooding in the first round by every node in $I$ sending the same message to all of its neighbours. In each subsequent round, nodes send the message to all of their neighbours from which they did not receive the message in the previous round. Flooding terminates when no node in $G$ sends a message in a round. The question of termination has not been settled - rather, non-termination is implicitly assumed to be possible. We show that flooding terminates on every finite graph. In the case of a single source $g_0$, flooding terminates in $e$ rounds if $G$ is bipartite and $j$ rounds with $e < j \leq e+d+1$ otherwise, where $e$ and $d$ are the eccentricity of $g_0$ and diameter of $G$ respectively. For communication/broadcast to all nodes, this is asymptotically time optimal and obviates the need for construction and maintenance of spanning structures. We extend to dynamic flooding initiated in multiple rounds with possibly multiple messages. The cases where a node only sends a message to neighbours from which it did not receive {\it any} message in the previous round, and where a node sends some highest ranked message to all neighbours from which it did not receive {\it that} message in the previous round, both terminate. All these cases also hold if the network graph loses edges over time. Non-terminating cases include asynchronous flooding, flooding where messages have fixed delays at edges, cases of multiple-message flooding and cases where the network graph acquires edges over time.
