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

来源：

SYSTEMS AND COMPUTERS IN JAPAN | 1994年 / 25卷 / 14期

关键词：

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

← 1 →