Investigating the Cost of Anonymity on Dynamic Networks
Investigating the Cost of Anonymity on Dynamic Networks
复制标题
调查动态网络的匿名成本
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
R. Baldoni
中科院分区：
文献类型：
--
作者：
Giuseppe Antonio Di Luna;R. Baldoni
在本文中，我们研究了同步动态网络中计算节点的难度，其中节点共享相同的标识符，它们通过使用无限带宽的广播进行通信，并且在每个同步轮中，网络拓扑可能会发生变化。事实证明，要在这种环境下进行计数，领导者的存在是必要的。我们关注动态网络的一个特别有趣的子集，即持久距离-G(PD)h，其中每个节点在各轮中与领导者的距离是固定的，并且该距离最多为 h。在这些网络中，动态直径 D 最多为 2h。我们证明 G(PD)2 中的计数轮数至少与网络大小 jVj 成对数。由于这个结果，我们表明依靠任何具有 D 常数的动态匿名网络。 jVj 至少需要 D+(log jVj) 轮，其中 (log jVj) 表示处理匿名性所需支付的额外成本。最好的时候
In this paper we study the diculty of counting nodes in a synchronous dynamic network where nodes share the same identier, they communicate by using a broadcast with unlimited bandwidth and, at each synchronous round, network topology may change. To count in such setting, it has been shown that the presence of a leader is necessary. We focus on a particularly interesting subset of dynamic networks, namely Persistent Distance -G(PD)h, in which each node has a xed distance from the leader across rounds and such distance is at most h. In these networks the dynamic diameter D is at most 2h. We prove the number of rounds for counting inG(PD)2 is at least logarithmic with respect to the network sizejVj. Thanks to this result, we show that counting on any dynamic anonymous network with D constant w.r.t. jVj takes at least D+(log jVj) rounds where (log jVj) represents the additional cost to be payed for handling anonymity. At the best