Two lower bounds in asynchronous distributed computation

DOI10.1016/0022-0000(91)90002-MzbMATH Open0731.68043OpenAlexW2148349970MaRDI QIDQ808249FDOQ808249

Zvi Galil, Pavol Ďuriš

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

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

zbMATH Keywords

lower boundsdistributed computationmessage complexitybidirectional ring of n anonymous processors

Mathematics Subject Classification ID

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

Cites Work

• Computing on an anonymous ring
• An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem
• Lower Bounds for Distributed Maximum-Finding Algorithms
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• Title not available (Why is that?)

Cited In (16)

• Title not available (Why is that?)
• Lower bounds to processor-time tradeoffs under bounded-speed message propagation
• Title not available (Why is that?)
• Efficiency of semisynchronous versus asynchronous networks
• Fooling views: a new lower bound technique for distributed computations under congestion
• Title not available (Why is that?)
• Hundreds of impossibility results for distributed computing
• Lower bounds on communication complexity in distributed computer networks
• Some lower bound results for decentralized extrema-finding in rings of processors
• Performing work with asynchronous processors: Message-delay-sensitive bounds
• Lower Bounds for Distributed Maximum-Finding Algorithms
• A lower bound for probabilistic distributed algorithms
• Computing functions on asynchronous anonymous networks
• On the bit complexity of distributed computations in a ring with a leader
• Computing on an anonymous ring
• Optimal lower bounds for some distributed algorithms for a complete network 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)