Two lower bounds in asynchronous distributed computation

DOI10.1016/0022-0000(91)90002-MMaRDI QIDQ808249zbMATH OpenOpenAlexFDO

Authors Pavol Ďuriš, Zvi Galil

Publication date 1991

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(91)90002-m

zbMATH Keywords

bidirectional ring of n anonymous processorsdistributed computationlower boundsmessage complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed algorithms (68W15)

Recommendations

• New lower bound techniques for distributed leader finding and other problems on rings of processors
• Lower Bounds for Distributed Maximum-Finding Algorithms
• Computing on an anonymous ring
• Some lower bound results for decentralized extrema-finding in rings of processors
• On the average communication complexity of asynchronous distributed algorithms

Cites work

• An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• Computing on an anonymous ring
• scientific article; zbMATH DE number 4028858 (Why is no real title available?)
• Lower Bounds for Distributed Maximum-Finding Algorithms

Cited in

(21)

• On the bit complexity of distributed computations in a ring with a leader
• Optimal lower bounds for some distributed algorithms for a complete network of processors
• Fooling views: a new lower bound technique for distributed computations under congestion
• Message lower bounds via efficient network synchronization
• Performing work with asynchronous processors: Message-delay-sensitive bounds
• Some lower bound results for decentralized extrema-finding in rings of processors
• Performing work with asynchronous processors, message-delay-sensitive bounds
• scientific article; zbMATH DE number 5547971 (Why is no real title available?)
• Lower Bounds for Distributed Maximum-Finding Algorithms
• Lower bounds on communication complexity in distributed computer networks
• A lower bound for probabilistic distributed algorithms
• scientific article; zbMATH DE number 4050994 (Why is no real title available?)
• Computing on an anonymous ring
• Efficiency of semisynchronous versus asynchronous networks
• scientific article; zbMATH DE number 1950667 (Why is no real title available?)
• Computing functions on asynchronous anonymous networks
• Lower bounds to processor-time tradeoffs under bounded-speed message propagation
• On the complexity of global computation in the presence of link failures: the general case
• Hundreds of impossibility results for distributed computing
• 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

This page was built for publication: Two lower bounds in asynchronous distributed computation

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