Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
复制标题
危险图中的乒乓球：使用纯代币的最优黑洞搜索
DOI：
10.1007/978-3-540-87779-0_16
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
N. Santoro
中科院分区：
文献类型：
--
作者：
P. Flocchini;D. Ilcinkas;N. Santoro
我们证明，对于黑洞搜索问题，纯令牌模型是计算功能强大的白板模型，而且是完全相同的复杂性。更准确地说，我们证明了一个团队的两个异步代理，每个人都赋予了一个相同的卵石（只能放置在节点上，每个节点不超过一个卵石）可以定位黑洞在任意网络的已知拓扑结构;这可以做到与Θ（nlogn）移动，其中是节点的数量，即使当链接不是FIFO。
We prove that, for the black hole search problem, the pure token model is computationally as powerful as the whiteboard model; furthermore the complexity is exactly the same. More precisely, we prove that a team oftwoasynchronous agents, each endowed with a single identical pebble (that can be placed only on nodes, and with no more than one pebble per node) can locate the black hole in an arbitrary network of known topology; this can be done withΘ(nlogn) moves, wherenis the number of nodes, even when the links are not FIFO.