A √N algorithm for mutual exclusion in decentralized systems

ACM Transactions on Computer Systems - Tập 3 Số 2 - Trang 145-159 - 1985
Masashi Maekawa1
1Department of Information Science, Faculty of Science, University of Tokyo, 7-3-1 Hongo, Bunkyo-ku, Tokyo 113, Japan

Tóm tắt

An algorithm is presented that uses only c√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.

Từ khóa


Tài liệu tham khảo

ALBERT A. A., 1968, An Introduction to Finite Projective Planes. Holt, Rinehart, and Winston

CARVALHO O. S., 1983, Commun. ACM, 26, 2

10.1145/359104.359108

GIFFORD D.K., 1979, Proceedings of the 7th Symposium on Operating System Principles (Pacific Grove, Calif., Dec. 10-12), 150

10.1145/359024.359029

LAMPORT L., 1978, Comput. Networks, 2, 95

10.1145/358527.358537

10.1145/357162.357163

SKEEN D., 1982, Proceedings o{ the 6th Berkeley Workshop on Distributed Data Management and Computer Networks (Feb., 69

10.1145/320071.320076

Thông tin
Thông tin xuất bản

ACM Transactions on Computer Systems

Tập 3 Số 2

145-159

Thông tin tác giả