Electing a leader in a ring with link failures
type: Item
instance of: scholarly article
title: Electing a leader in a ring with link failures
zbMATH Open document ID: 0591.68021
DOI: 10.1007/BF00290707
author: Oded Goldreich
author: Liuba Shrira
published in: Acta Informatica
publication date: 1987-01-01T00:00:00Z
review text: We investigate the message complexity of electing a leader in a ring of asynchronous processors. Our work deviates from the previous works on electing a leader in that we consider the effect of link failures. A link is said to fail if some message sent through it never reaches its destination. We distinguish the case where n is known from the case n unknown. Our main result is an O(n log n) algorithm for electing a leader on an n-processor ring (the case n is known).
Mathematics Subject Classification ID: 68N25
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3949686
zbMATH Keywords: distributed computation
zbMATH Keywords: asynchronous networks
zbMATH Keywords: message complexity
zbMATH Keywords: ring of asynchronous processors
zbMATH Keywords: link failures
zbMATH Keywords: algorithm
MaRDI profile type: Publication
cites work: An improved algorithm for decentralized extrema-finding in circular configurations of processes
cites work: An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
cites work: Electing a leader in a synchronous ring
cites work: A Distributed Algorithm for Minimum-Weight Spanning Trees
cites work: Decentralized extrema-finding in circular configurations of processors
cites work: The multi-tree approach to reliability in distributed networks
cites work: On describing the behavior and implementation of distributed systems
cites work: An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem
Recommended article: Electing a leader in a synchronous ring
Recommended article: Q4037443
Recommended article: Leader election in rings of ambient processes
Recommended article: Improved bounds for electing a leader in a synchronous ring
Recommended article: Compact deterministic self-stabilizing leader election on a ring: the exponential advantage of being talkative
Recommended article: Time-Optimal Self-stabilizing Leader Election on Rings in Population Protocols
description: scientific article; zbMATH DE number 3949686