Decentralized extrema-finding in circular configurations of processors

DOI10.1145/359024.359029zbMath0444.68022OpenAlexW1999527722MaRDI QIDQ3888516

J. B. Sinclair, Daniel S. Hirschberg

Publication date: 1980

Published in: Communications of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/359024.359029

zbMATH Keywords

decentralized algorithmsdistributed systemoperating systems

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of operating systems (68N25)

Related Items (29)

Distributed algorithm for extrema-finding in circular configuration of processors ⋮ Strictly in-place algorithms for permuting and inverting permutations ⋮ New protocols for the election of a leader in a ring ⋮ Some lower bound results for decentralized extrema-finding in rings of processors ⋮ An improved election algorithm in chordal ring networks ⋮ AN IMPROVED ALGORITHM FOR SUBDIVISION TRAVERSAL WITHOUT EXTRA STORAGE ⋮ Cost distribution of the Chang-Roberts leader election algorithm and related problems ⋮ Distributed tree comparison with nodes of limited memory ⋮ Four shades of deterministic leader election in anonymous networks ⋮ Fast leader election in anonymous rings with bounded expected delay ⋮ Efficient parallel k selection algorithm ⋮ The communication complexity for decentralized evaluation of functions ⋮ Symmetry breaking in distributed networks ⋮ Communication and time complexity of a distributed election protocol ⋮ How much memory is needed for leader election ⋮ A simple, efficient algorithm for maximum finding on rings ⋮ Knowledge, level of symmetry, and time of leader election ⋮ Leader election for anonymous asynchronous agents in arbitrary networks ⋮ Impact of knowledge on election time in anonymous networks ⋮ Distributed election in a circle without a global sense of orientation ⋮ On the message complexity of distributed problems ⋮ Some problems in distributed computational geometry ⋮ Topology recognition and leader election in colored networks ⋮ Computing on a partially eponymous ring ⋮ Exact communication costs for consensus and leader in a tree ⋮ On the complexity of computation in the presence of link failures: The case of a ring ⋮ Topology recognition with advice ⋮ Electing a leader in a ring with link failures ⋮ Anonymous meeting in networks

This page was built for publication: Decentralized extrema-finding in circular configurations of processors