Self-stabilizing silent disjunction in an anonymous network

被引:1
作者
Datta, Ajoy K. [1 ]
Devismes, Stephane [2 ]
Larmore, Lawrence L. [1 ]
机构
[1] Univ Nevada Las Vegas, Las Vegas, NV USA
[2] Univ Joseph Fourier, VERIMAG UMR 5104, Grenoble, France
关键词
Anonymous network; Disjunction; Self-stabilization; Silence; Unfair daemon; LEADER ELECTION; ALGORITHM; CONSTRUCTION; SYSTEMS; TREES;
D O I
10.1016/j.tcs.2016.12.012
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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.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 0(n) rounds, where n is the size of the network, and the memory requirement per process is 0 (log D + Delta) where D and Delta are, respectively, the diameter, and the maximum degree of the network. (C) 2016 Elsevier B.V. All rights reserved.
引用
收藏
页码:51 / 72
页数:22
相关论文
共 34 条
[1]  
Altisen K., 2016, INFORM COMPUT
[2]  
ANGLUIN D, 1980, 12TH P ANN ACM S THE, P82
[3]  
[Anonymous], 1998, CHICAGO J THEOR COMP
[4]   DISTRIBUTED RESET [J].
ARORA, A ;
GOUDA, M .
IEEE TRANSACTIONS ON COMPUTERS, 1994, 43 (09) :1026-1038
[5]  
Awerbuch B., 1993, Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, P652, DOI 10.1145/167088.167256
[6]  
AWERBUCH B, 1991, PROCEEDINGS - 32ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, P268, DOI 10.1109/SFCS.1991.185378
[7]  
Burman J, 2007, LECT NOTES COMPUT SC, V4731, P92
[8]   A self-stabilizing k-clustering algorithm for weighted graphs [J].
Caron, Eddy ;
Datta, Ajoy K. ;
Depardon, Benjamin ;
Larmore, Lawrence L. .
JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2010, 70 (11) :1159-1173
[9]   A SELF-STABILIZING ALGORITHM FOR CONSTRUCTING SPANNING-TREES [J].
CHEN, NS ;
YU, HP ;
HUANG, ST .
INFORMATION PROCESSING LETTERS, 1991, 39 (03) :147-151
[10]   SELF-STABILIZING DEPTH-1ST SEARCH [J].
COLLIN, Z ;
DOLEV, S .
INFORMATION PROCESSING LETTERS, 1994, 49 (06) :297-301