The computational power of simple protocols for self-awareness on graphs
DOI10.1016/j.tcs.2012.08.026zbMath1358.68034OpenAlexW2092894787WikidataQ57608028 ScholiaQ57608028MaRDI QIDQ392008
Ioannis Chatzigiannakis, Stavros Nikolaou, Othon Michail, Paul G. Spirakis
Publication date: 13 January 2014
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.08.026
complexitygraph propertydiffuse computationfinite-state agentintermittent communicationpassive mobilitypopulation protocolself-awarenessstable computation
Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Network protocols (68M12)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Computational models for networks of tiny artifacts: a survey
- Mediated population protocols
- Passively mobile communicating machines that use restricted space
- Causality, influence, and computation in possibly disconnected synchronous dynamic networks
- On the convergence of population protocols when population goes to infinity
- Characterizations of classes of graphs recognizable by local computations
- The computational power of population protocols
- Computation in networks of passively mobile finite-state sensors
- Fast computation by population protocols with a leader
- Semigroups, Presburger formulas, and languages
- Distributed computation in dynamic networks
- Recent Advances in Population Protocols
- The Dynamics of Probabilistic Population Protocols
- All Symmetric Predicates in NSPACE(n 2) Are Stably Computable by the Mediated Population Protocol Model
- Mediated Population Protocols
- Self-stabilizing systems in spite of distributed control
- Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
- Computation in networks of passively mobile finite-state sensors
This page was built for publication: The computational power of simple protocols for self-awareness on graphs
