UNIFORM SELF-STABILIZING ALGORITHMS FOR MUTUAL EXCLUSION

被引:0
作者
NISHIKAWA, N [1 ]
MASUZAWA, T [1 ]
TOKURA, N [1 ]
机构
[1] OSAKA UNIV,FAC ENGN SCI,TOYONAKA,OSAKA 560,JAPAN
关键词
DISTRIBUTED ALGORITHM; ALGORITHM; SELF-STABILIZING; MUTUAL EXCLUSION; PROBABLISTIC ALGORITHM;
D O I
暂无
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
A self-stabilizing algorithm is a distributed algorithm that can solve problems, even when started in any arbitrary network configuration. This paper describes a self-stabilizing algorithm that solves mutual exclusion problems for three networks and complete networks. In a tree network or in a complete network, because of their symmetrical nature, mutual exclusion problems cannot be solved by uniform deterministic algorithms (all processors execute the same programs and do not assume the existence of mutually distinct identifiers). Thus, the algorithms introduced in this paper are superior to the existing ones in the following respects: (1) uniformity of algorithms; (2) forwardness of little atomic action of processor (read/write demon); and (3) finiteness of the state number of the processors.
引用
收藏
页码:12 / 21
页数:10
相关论文
共 7 条
  • [1] TOKEN SYSTEMS THAT SELF-STABILIZE
    BROWN, GM
    GOUDA, MG
    WU, CL
    [J]. IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (06) : 845 - 852
  • [2] SELF-STABILIZING SYSTEMS IN SPITE OF DISTRIBUTED CONTROL
    DIJKSTRA, EW
    [J]. COMMUNICATIONS OF THE ACM, 1974, 17 (11) : 643 - 644
  • [3] DOLEV S, 1990, 9TH P ANN ACM S PRIN, P103
  • [4] ISRAELI A, 1990, 9TH P ANN ACM S PRIN, P119
  • [5] ISRAELI A, 1990, 4TH P INT WORKSH DIS, P1
  • [6] KATZ S, 1990, 9TH P ANN ACM S PRIN, P91
  • [7] KRUIJERHSM, 1978, INFORMATION PROCESSI, V8, P91