Lower Bounds for Distributed Maximum-Finding Algorithms

DOI10.1145/1634.1889zbMATH Open0628.68046OpenAlexW2001357803WikidataQ58330005 ScholiaQ58330005MaRDI QIDQ3765249FDOQ3765249

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

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

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)

Cited In (26)

• 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
• Title not available (Why is that?)
• On the bit complexity of distributed computations in a ring with a leader
• 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)