New lower bound techniques for distributed leader finding and other problems on rings of processors

DOI10.1016/0304-3975(91)90193-6zbMATH Open0732.68048OpenAlexW2006888470WikidataQ59568030 ScholiaQ59568030MaRDI QIDQ808701FDOQ808701

Hans L. Bodlaender

Publication date: 1991

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://dspace.library.uu.nl/handle/1874/16571

Recommendations

• Two lower bounds in asynchronous distributed computation
• Some lower bound results for decentralized extrema-finding in rings of processors
• scientific article
• Computing on an anonymous ring
• Lower Bounds for Distributed Maximum-Finding Algorithms

zbMATH Keywords

randomized algorithmslower bounddistributed algorithmleader electionasynchronous ring of processors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10)

Cites Work

• Electing a leader in a synchronous ring
• Computing on an anonymous ring
• Title not available (Why is that?)
• An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem
• An improved algorithm for decentralized extrema-finding in circular configurations of processes
• Lower Bounds for Distributed Maximum-Finding Algorithms
• An O(n log n) unidirectional distributed algorithm for extrema finding in a circle
• A lower bound for probabilistic distributed algorithms
• The Bit Complexity of Randomized Leader Election on a Ring
• Title not available (Why is that?)
• Randomized function evaluation on a ring
• A better lower bound for distributed leader finding in bidirectional asynchronous rings of processors
• Average number of messages for distributed leader-fitting in rings of processors
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (12)

• Finding cut-offs in leaderless rendez-vous protocols is easy
• Hundreds of impossibility results for distributed computing
• Some lower bound results for decentralized extrema-finding in rings of processors
• Tight lower bounds for probabilistic solitude verification on anonymous rings
• TOPOLOGICAL CONSTRAINTS FOR SENSE OF DIRECTION
• Lower Bounds for Distributed Maximum-Finding Algorithms
• Fast leader election in anonymous rings with bounded expected delay
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the bit complexity of distributed computations in a ring with a leader
• Title not available (Why is that?)
• Average number of messages for distributed leader-fitting in rings of processors

This page was built for publication: New lower bound techniques for distributed leader finding and other problems on rings of processors

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