Randomized function evaluation on a ring

DOI10.1007/BF01784021MaRDI QIDQ916384zbMATH OpenOpenAlexFDO

Authors Elsie Sterbin Gottlieb

Publication date 1989

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01784021

zbMATH Keywords

randomizationlower boundsdistributed algorithmsnondeterminismasynchronycommunication complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Communication theory (94A05)

Recommendations

• scientific article; zbMATH DE number 4055049
• Better computing on the anonymous ring
• Nondeterministic communication complexity of random Boolean functions (extended abstract)
• Average and randomized communication complexity
• A communication-randomness tradeoff for two-processor systems

Cites work

• scientific article; zbMATH DE number 3065066 (Why is no real title available?)
• A lower bound for probabilistic distributed algorithms
• 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
• Lower Bounds for Distributed Maximum-Finding Algorithms
• Optimal Algorithms for Probabilistic Solitude Detection on Anonymous Rings
• Symmetry breaking in distributed networks
• The Bit Complexity of Randomized Leader Election on a Ring

Cited in

(5)

• Anonymous wireless rings
• Hundreds of impossibility results for distributed computing
• New lower bound techniques for distributed leader finding and other problems on rings of processors
• scientific article; zbMATH DE number 4055049 (Why is no real title available?)
• SPRING: Fast Pseudorandom Functions from Rounded Ring Products

This page was built for publication: Randomized function evaluation on a ring

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