Leader election in plane cellular automata, only with left-right global convention

DOI10.1016/J.TCS.2004.02.009zbMath1068.68090OpenAlexW2057053666MaRDI QIDQ596068

Christophe Papazian, Codrin Nichitiu, Eric Rémila

Publication date: 10 August 2004

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2004.02.009

zbMATH Keywords

Distributed algorithmsEuclidean cellular automataGraph automataHyperbolic cellular automataLeader election

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cellular automata (computational aspects) (68Q80) Graph algorithms (graph-theoretic aspects) (05C85) Distributed systems (68M14) Distributed algorithms (68W15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Distributed enumeration
• Solvability of the asynchronous ranking problem
• Coverings and minors: Application to local computations in graphs
• Algorithms for Leader Election by Cellular Automata
• Cellular graph automata. I. basic concepts, graph property measurement, closure properties
• Leader election in d-dimensional CA in time diam log(diam)
• Computing functions on asynchronous anonymous networks
• A perimeter--time CA for the queen bee problem
• NP problems are tractable in the space of cellular automata in the hyperbolic plane

This page was built for publication: Leader election in plane cellular automata, only with left-right global convention