IMPROVED ALGORITHM FOR DECENTRALIZED EXTREMA-FINDING IN CIRCULAR CONFIGURATIONS OF PROCESSES

被引：185

作者：

CHANG, E ^{[1
]}

ROBERTS, R ^{[1
]}

机构：

[1] UNIV TORONTO,TORONTO M5S 1A1,ONTARIO,CANADA

来源：

COMMUNICATIONS OF THE ACM | 1979年 / 22卷 / 05期

关键词：

decentralized algorithms; distributed systems; operating systems;

D O I：

10.1145/359104.359108

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

This note presents an improvement to LeLann's algorithm for finding the largest (or smallest) of a set of uniquely numbered processes arranged in a circle, in which no central controller exists and the number of processes is not known a priori. This decentralized algorithm uses a technique of selective message extinction in order to achieve an average number of message passes of order (n log n) rather than O(n2). © 1979, ACM. All rights reserved.

引用

页码：281 / 283

页数：3