Self-stabilizing silent disjunction in an anonymous network

详细信息    查看全文

• 作者：Ajoy K. Datta^a ; Sté ; phane Devismes^b ; ^{Stephane.Devismes@univ-grenoble-alpes.fr} ; Lawrence L. Larmore^a
• 关键词：Anonymous network ; Disjunction ; Self-stabilization ; Silence ; Unfair daemon
• 刊名：Theoretical Computer Science
• 出版年：2017
• 出版时间：22 February 2017
• 年：2017
• 卷：665
• 期：Complete
• 页码：51-72
• 全文大小：684 K
• 卷排序：665

文摘

In this paper, we give a distributed silent self-stabilizing algorithm, DISJ, for the disjunction problem in a connected network. In this problem, each process x   has an input bit x.inx.in, assigned by the application layer, and each process must compute the disjunction of the input bits of all processes. DISJ is uniform, and works in an anonymous network under the distributed unfair daemon. The stabilization time of DISJ is O(n)O(n) rounds, where n   is the size of the network, and the memory requirement per process is O(log⁡D+Δ)O(log⁡D+Δ) where DD and Δ are, respectively, the diameter, and the maximum degree of the network.