Randomized function evaluation on a ring

DOI10.1007/BF01784021zbMATH Open0703.68057OpenAlexW2918030272MaRDI QIDQ916384FDOQ916384

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

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

zbMATH Keywords

randomizationlower boundsdistributed algorithmsnondeterminismasynchronycommunication complexity

Mathematics Subject Classification ID

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

Cites Work

• Computing on an anonymous ring
• An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem
• Title not available (Why is that?)
• Symmetry breaking in distributed networks
• 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
• Optimal Algorithms for Probabilistic Solitude Detection on Anonymous Rings

Cited In (5)

• SPRING: Fast Pseudorandom Functions from Rounded Ring Products
• Hundreds of impossibility results for distributed computing
• Anonymous wireless rings
• Title not available (Why is that?)
• New lower bound techniques for distributed leader finding and other problems on rings of processors

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)