Lower Bounds for Distributed Maximum-Finding Algorithms

DOI10.1145/1634.1889MaRDI QIDQ3765249zbMATH OpenOpenAlexWikidataFDO

Authors Ephraim Korach, Doron Rotem, Jan Pachl

Publication date 1984

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

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

zbMATH Keywords

lower boundsdistributed algorithmsmessage complexitycommunication ringselection algorithmsmaximum label in a circular configuration of n labeled processesnumber of messages

Mathematics Subject Classification ID

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

Recommendations

• Two lower bounds in asynchronous distributed computation
• A lower bound for probabilistic distributed algorithms
• Some lower bound results for decentralized extrema-finding in rings of processors
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• New lower bound techniques for distributed leader finding and other problems on rings of processors

Cited in

(27)

• Message terminating algorithms for anonymous rings of unknown size
• Bit-optimal election in synchronous rings
• Randomized function evaluation on a ring
• Language complexity on the synchronous anonymous ring
• Fooling views: a new lower bound technique for distributed computations under congestion
• Sense of direction in processor networks
• Lower Bounds for Distributed Sketching of Maximal Matchings and Maximal Independent Sets
• Distributed election in complete networks
• Some lower bound results for decentralized extrema-finding in rings of processors
• Optimal cost-sensitive distributed minimum spanning tree algorithm
• Distributed maximum maintenance on hierarchically divided graphs
• Towards optimal distributed election on chordal rings
• Efficient elections in chordal ring networks
• Asymptotically optimal election on weighted rings
• Time vs bits
• A lower bound for probabilistic distributed algorithms
• Fast leader election in anonymous rings with bounded expected delay
• scientific article; zbMATH DE number 3850459 (Why is no real title available?)
• On the bit complexity of distributed computations in a ring with a leader
• New bounds for the controller problem
• New lower bound techniques for distributed leader finding and other problems on rings of processors
• Two lower bounds in asynchronous distributed computation
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• Asymptotically Optimal Election on Weighted Rings
• On the message complexity of distributed problems
• A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors
• A simple, efficient algorithm for maximum finding on rings

This page was built for publication: Lower Bounds for Distributed Maximum-Finding Algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3765249)