An O(n log n) unidirectional distributed algorithm for extrema finding in a circle

DOI10.1016/0196-6774(82)90023-2zbMath0493.68074OpenAlexW1967333679WikidataQ29306301 ScholiaQ29306301MaRDI QIDQ3956422

Michael Rodeh, Danny Dolev, Maria M. Klawe

Publication date: 1982

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0196-6774(82)90023-2

zbMATH Keywords

distributed systemsmaximum numberasynchronous communicating processescircular arrangement of n uniquely numbered processes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of operating systems (68N25) Discrete mathematics in relation to computer science (68R99)

Related Items (38)

Strictly in-place algorithms for permuting and inverting permutations ⋮ An efficient algorithm for computing bisimulation equivalence ⋮ New protocols for the election of a leader in a ring ⋮ Asymptotically optimal election on weighted rings ⋮ On the bit complexity of distributed computations in a ring with a leader ⋮ Language complexity on the synchronous anonymous ring ⋮ Some lower bound results for decentralized extrema-finding in rings of processors ⋮ An improved election algorithm in chordal ring networks ⋮ Exploiting interleaving semantics in symbolic state-space generation ⋮ A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors ⋮ Cost distribution of the Chang-Roberts leader election algorithm and related problems ⋮ Distributed algorithms for selection in sets ⋮ Time vs bits ⋮ Formal verification of a leader election protocol in process algebra ⋮ Fast leader election in anonymous rings with bounded expected delay ⋮ An automata-theoretic approach to the verification of distributed algorithms ⋮ Efficient parallel k selection algorithm ⋮ The communication complexity for decentralized evaluation of functions ⋮ Bit-optimal election in synchronous rings ⋮ Randomized function evaluation on a ring ⋮ Symmetry breaking in distributed networks ⋮ Hundreds of impossibility results for distributed computing ⋮ Towards optimal distributed election on chordal rings ⋮ Data flow analysis of asynchronous systems using infinite abstract domains ⋮ An Abstraction Technique for Parameterized Model Checking of Leader Election Protocols: Application to FTSP ⋮ A simple, efficient algorithm for maximum finding on rings ⋮ Anonymous wireless rings ⋮ Unnamed Item ⋮ Quasi-Monotonic Sequences: Theory, Algorithms and Applications ⋮ Distributed election in a circle without a global sense of orientation ⋮ On the message complexity of distributed problems ⋮ Efficient elections in chordal ring networks ⋮ AN EFFICIENT FULLY SYMBOLIC BISIMULATION ALGORITHM FOR NON-DETERMINISTIC SYSTEMS ⋮ Asymptotically Optimal Election on Weighted Rings ⋮ Two lower bounds in asynchronous distributed computation ⋮ On the complexity of computation in the presence of link failures: The case of a ring ⋮ New lower bound techniques for distributed leader finding and other problems on rings of processors ⋮ Electing a leader in a ring with link failures

This page was built for publication: An O(n log n) unidirectional distributed algorithm for extrema finding in a circle