Better computing on the anonymous ring

DOI10.1016/0196-6774(91)90002-GMaRDI QIDQ3361868zbMATH OpenOpenAlexFDO

Authors Hagit Attiya, Marc Snir

Publication date 1991

Published in Journal of Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0196-6774(91)90002-g

zbMATH Keywords

asynchronous deterministic algorithmasynchronous probabilistic algorithmaverage complexitylower boundMonte-Carlo asynchronous algorithm

Mathematics Subject Classification ID

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

Recommendations

• Computing on an anonymous ring
• Computing functions on asynchronous anonymous networks
• Gap Theorems for Distributed Computation
• The distributed bit complexity of the ring: From the anonymous to the non-anonymous case
• Message terminating algorithms for anonymous rings of unknown size

Cited in

(38)

• Computing on a partially eponymous ring
• On the round complexity of Byzantine agreement without initial set-up
• Language complexity on the synchronous anonymous ring
• Average number of messages for distributed leader-fitting in rings of processors
• Perfect broadcasting in unlabeled networks
• The distributed bit complexity of the ring: From the anonymous to the non-anonymous case
• Sorting and election in anonymous asynchronous rings.
• Impact of knowledge on election time in anonymous networks
• Leader election for anonymous asynchronous agents in arbitrary networks
• Broadcasting in unlabeled hypercubes with a linear number of messages.
• Anonymous meeting in networks
• Anonymous networks, randomization = 2-hop coloring
• Anonymous processors with synchronous shared memory: Monte Carlo algorithms
• String recognition on anonymous rings
• scientific article; zbMATH DE number 4055049 (Why is no real title available?)
• scientific article; zbMATH DE number 4058846 (Why is no real title available?)
• Computing on an anonymous ring
• scientific article; zbMATH DE number 17531 (Why is no real title available?)
• Gap Theorems for Distributed Computation
• scientific article; zbMATH DE number 177819 (Why is no real title available?)
• Tight lower bounds for probabilistic solitude verification on anonymous rings
• Network Orientation
• Computing functions on asynchronous anonymous networks
• Assigning labels in an unknown anonymous network with a leader
• Hundreds of impossibility results for distributed computing
• Distributed tree comparison with nodes of limited memory
• Learning a ring cheaply and fast
• On recognizing a string on an anonymous ring
• Topology recognition and leader election in colored networks
• Four shades of deterministic leader election in anonymous networks
• Variations of the Itai-Rodeh Algorithm for Computing Anonymous Ring Size
• How much memory is needed for leader election
• Anonymous wireless rings
• Message terminating algorithms for anonymous rings of unknown size
• Minimum algorithm sizes for the gathering and related problems of autonomous mobile robots
• Content-oblivious leader election on rings
• Scattering on a ring of processors
• Randomized function evaluation on a ring

This page was built for publication: Better computing on the anonymous ring

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