OPTIMAL ALGORITHM FOR MUTUAL EXCLUSION IN MESH-CONNECTED COMPUTER-NETWORKS

被引：2

作者：

CHAUDHURI, P

机构：

[1] School of Computer Science and Engineering, The University of New South Wales, Kensington, NSW 2033

来源：

COMPUTER COMMUNICATIONS | 1991年 / 14卷 / 10期

关键词：

DISTRIBUTED ALGORITHM; MUTUAL EXCLUSION; MESSAGE EXCHANGE; DELAY; OPTIMALITY;

D O I：

10.1016/0140-3664(91)90052-3

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

A distributed algorithm is presented that realizes mutual exclusion among n nodes in a mesh-connected computer network. The nodes communicate by using messages only, and there is no global controller. The algorithm requires at most 3.5 square-root n messages per mutual exclusion invocation under light demand, and reduces to approximately four messages under heavy demand. The time required to achieve mutual exclusion is shown to be minimal under some general assumptions.

引用

页码：627 / 632

页数：6

共 12 条

[1]

CARVALHO O, 1983, COMMUN ACM, V26, P147

[2]

Coffman Jr E. G., 1973, OPERATING SYSTEMS TH

[3]

Hansen Per Brinch, 1973, OPERATING SYSTEM PRI

[4] A DISTRIBUTED ALGORITHM FOR MUTUAL EXCLUSION IN AN ARBITRARY NETWORK [J].