How much memory is needed for leader election

DOI10.1007/S00446-011-0131-YMaRDI QIDQ661049zbMATH OpenOpenAlexFDO

Authors Emanuele G. Fusco, Andrzej Pelc

Publication date 6 February 2012

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00446-011-0131-y

zbMATH Keywords

anonymous graphsleader electionmemory

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• How much memory is needed for leader election
• The space complexity of leader election in anonymous networks
• Self-stabilizing weak leader election in anonymous trees using constant memory per edge
• Time vs. information tradeoffs for leader election in anonymous trees

Cites work

• An O ( n log n ) Unidirectional Algorithm for the Circular Extrema Problem
• Anonymous wireless rings
• Better computing on the anonymous ring
• Comparison of initial conditions for distributed algorithms on anonymous networks
• Computing anonymously with arbitrary knowledge
• Computing Boolean functions on anonymous networks
• Computing on an anonymous ring
• Decentralized extrema-finding in circular configurations of processors
• Delays induce an exponential memory gap for rendezvous in trees
• Deterministic Rendezvous in Trees with Little Memory
• Electing a leader in a synchronous ring
• Foundations of Software Science and Computation Structures
• How to meet when you forget: log-space rendezvous in arbitrary graphs
• scientific article; zbMATH DE number 1756017 (Why is no real title available?)
• scientific article; zbMATH DE number 2086374 (Why is no real title available?)
• scientific article; zbMATH DE number 2113969 (Why is no real title available?)
• Labelled (Hyper)Graphs, Negotiations and the Naming Problem
• Leader Election in Ad Hoc Radio Networks: A Keen Ear Helps
• Log-Logarithmic Selection Resolution Protocols in a Multiple Access Channel
• Proving Distributed Algorithms for Mobile Agents: Examples of Spanning Tree Computation in Anonymous Networks
• Randomized Rendez-Vous with Limited Memory
• SOFSEM 2005: Theory and Practice of Computer Science
• Sorting and election in anonymous asynchronous rings.
• Space Lower Bounds for Maze Threadability on Restricted Machines
• STACS 2004
• Undirected connectivity in log-space
• Universal covers of graphs: Isomorphism to depth \(n-1\) implies isomorphism to all depths
• Universal traversal sequences with backtracking.

Cited in

(10)

• Leader election for anonymous asynchronous agents in arbitrary networks
• Topology recognition with advice
• Anonymous meeting in networks
• Distributed tree comparison with nodes of limited memory
• The space complexity of leader election in anonymous networks
• How much memory is needed for leader election
• Distributed tree comparison with nodes of limited memory
• Some bounded degree communication networks and optimal leader election
• Topology recognition and leader election in colored networks
• Four shades of deterministic leader election in anonymous networks

This page was built for publication: How much memory is needed for leader election

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