A near-optimal multistage distributed algorithm for finding leaders in clustered chordal rings
type: Item
instance of: scholarly article
title: A near-optimal multistage distributed algorithm for finding leaders in clustered chordal rings
zbMATH Open document ID: 0813.68110
DOI: 10.1016/0020-0255(94)90071-X
published in: Information Sciences
publication date: 1994-07-26T00:00:00Z
review text: In a distributed computer system, each processor has an identity number known only to the processor itself. The processor that has the highest identity is the leader of the network. The problem of finding the leader is called an election algorithm. Chordal rings are a class of networks with a ring topology and with additional edges (chords) connecting processors with distances of more than two along the ring. A new nearly optimal in number of messages and links multistage electron algorithm for a clustered chordal ring is proposed in this paper. An upper complexity bound in the author's algorithm are \(O(G(n),n)\) for messages and \(G(n)\) chords at each processor. The function \(G(n)\) is defined recursively and has a very low speed of increasing. For all \(n < 2 60536\) the value \(G(n) < 5\). This result enhances many previous results by other authors.
Mathematics Subject Classification ID: 68W10
Mathematics Subject Classification ID: 68M10
zbMATH DE Number: 611307
zbMATH Keywords: chordal rings
zbMATH Keywords: distributed computer system
zbMATH Keywords: election algorithm
author: Yi Pan
reviewed by: Anatoly V. Anisimov
MaRDI profile type: Publication
cites work: Efficient elections in chordal ring networks
cites work: Towards optimal distributed election on chordal rings
cites work: An improved election algorithm in chordal ring networks
cites work: Q4891897
cites work: An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem
description: scientific article; zbMATH DE number 611307