A SQUARE-ROOT-N ALGORITHM FOR MUTUAL EXCLUSION IN DECENTRALIZED SYSTEMS

被引：393

作者：

MAEKAWA, M

机构：

[1] Univ of Tokyo, Dep of Information, Science, Tokyo, Jpn, Univ of Tokyo, Dep of Information Science, Tokyo, Jpn

来源：

ACM TRANSACTIONS ON COMPUTER SYSTEMS | 1985年 / 3卷 / 02期

关键词：

COMPUTER PROGRAMMING - Algorithms;

D O I：

10.1145/214438.214445

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

An algorithm is presented that uses only c ROOT N messages to create mutual exclusion in a computer network, where N is the number of nodes and c a constant between 3 and 5. The algorithm is symmetric and allows fully parallel operation.

引用

页码：145 / 159

页数：15

共 11 条

[1]

Albert A., 1968, INTRO FINITE PROJECT

[2]

CARVALHO OSF, 1983, COMMUN ACM, V26, P146

[3] IMPROVED ALGORITHM FOR DECENTRALIZED EXTREMA-FINDING IN CIRCULAR CONFIGURATIONS OF PROCESSES [J].

CHANG, E ;

ROBERTS, R .

COMMUNICATIONS OF THE ACM, 1979, 22 (05) :281-283

[4]

GARCIAMOLINA H, 1983, 311 PRINC U DEP EL E

[5]

GIFFORD DK, 1979, 7TH P S OP SYST PRIN, P150

[6] DECENTRALIZED EXTREMA-FINDING IN CIRCULAR CONFIGURATIONS OF PROCESSORS [J].

HIRSCHBERG, DS ;

SINCLAIR, JB .

COMMUNICATIONS OF THE ACM, 1980, 23 (11) :627-628

[7] IMPLEMENTATION OF RELIABLE DISTRIBUTED MULTIPROCESS SYSTEMS [J].

LAMPORT, L .

COMPUTER NETWORKS AND ISDN SYSTEMS, 1978, 2 (02) :95-114

[8] AN OPTIMAL ALGORITHM FOR MUTUAL EXCLUSION IN COMPUTER-NETWORKS [J].

RICART, G ;

AGRAWALA, AK .

COMMUNICATIONS OF THE ACM, 1981, 24 (01) :9-17

[9] SYNCHRONIZATION IN DISTRIBUTED PROGRAMS [J].

SCHNEIDER, FB .

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS, 1982, 4 (02) :125-148

[10]

SKEEN D, 1982, 6TH P BERK WORKSH DI, P69

← 1 2 →