Computing on an anonymous ring
From MaRDI portal
Publication:3813292
DOI10.1145/48014.48247zbMath0662.68035OpenAlexW2089155578MaRDI QIDQ3813292
Marc Snir, Hagit Attiya, Manfred K. Warmuth
Publication date: 1988
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/48014.48247
Synchronizationlower boundscoordinationdistributed algorithmscommunication complexitysynchronous modelcomputable function
Analysis of algorithms and problem complexity (68Q25) Theory of operating systems (68N25) Theory of software (68N99) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)
Related Items (55)
Minimal sense of direction in regular networks ⋮ Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths ⋮ Simple and fast approximate counting and leader election in populations ⋮ Finding routes in anonymous sensor networks ⋮ Language complexity on the synchronous anonymous ring ⋮ Multicast Network Design Game on a Ring ⋮ Anonymous asynchronous systems: the case of failure detectors ⋮ Labeled versus unlabeled distributed Cayley networks ⋮ Distributed tree comparison with nodes of limited memory ⋮ Distributed computing on transitive networks: The torus ⋮ Computing with infinitely many processes ⋮ Almost universal anonymous rendezvous in the plane ⋮ Four shades of deterministic leader election in anonymous networks ⋮ Tight bounds for synchronous communication of information using bits and silence ⋮ How to meet when you forget: log-space rendezvous in arbitrary graphs ⋮ Computing on anonymous networks with sense of direction ⋮ Uniform atomic broadcast and consensus in fully anonymous synchronous systems with crash failures ⋮ Activating anonymous ad hoc radio networks ⋮ Randomized function evaluation on a ring ⋮ Computing functions on asynchronous anonymous networks ⋮ Assigning labels in an unknown anonymous network with a leader ⋮ Distributed computing on oriented anonymous hypercubes with faulty components ⋮ Hundreds of impossibility results for distributed computing ⋮ A knowledge-based analysis of global function computation ⋮ How much memory is needed for leader election ⋮ Knowledge, level of symmetry, and time of leader election ⋮ Anonymous wireless rings ⋮ Message terminating algorithms for anonymous rings of unknown size ⋮ Deterministic leader election takes \(\Theta (D + \log n)\) bit rounds ⋮ Wang tilings and distributed verification on anonymous torus networks ⋮ Consensus in anonymous asynchronous systems with crash-recovery and omission failures ⋮ Leader election for anonymous asynchronous agents in arbitrary networks ⋮ Impact of knowledge on election time in anonymous networks ⋮ Improved bounds on equilibria solutions in the network design game ⋮ Unnamed Item ⋮ On the Microscopic View of Time and Messages ⋮ An Algorithmic Theory of Mobile Agents ⋮ Topology recognition and leader election in colored networks ⋮ Weak models of distributed computing, with connections to modal logic ⋮ Computing on a partially eponymous ring ⋮ Perfect broadcasting in unlabeled networks ⋮ Symmetries and sense of direction in labeled graphs ⋮ Self-stabilizing ring orientation using constant space ⋮ Graphs with prescribed local neighborhoods of their universal coverings ⋮ Rapid convergence of a local load balancing algorithm for asynchronous rings ⋮ On the round complexity of Byzantine agreement without initial set-up ⋮ Computing in totally anonymous asynchronous shared memory systems ⋮ Broadcasting in unlabeled hypercubes with a linear number of messages. ⋮ Analysis of fully distributed splitting and naming probabilistic procedures and applications ⋮ Analysis of Fully Distributed Splitting and Naming Probabilistic Procedures and Applications ⋮ Two lower bounds in asynchronous distributed computation ⋮ On the complexity of computation in the presence of link failures: The case of a ring ⋮ New lower bound techniques for distributed leader finding and other problems on rings of processors ⋮ Topology recognition with advice ⋮ Sense of direction in distributed computing
This page was built for publication: Computing on an anonymous ring
