The computational power of simple protocols for self-awareness on graphs
From MaRDI portal
Publication:392008
DOI10.1016/j.tcs.2012.08.026zbMath1358.68034WikidataQ57608028 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
complexity; graph property; diffuse computation; finite-state agent; intermittent communication; passive mobility; population protocol; self-awareness; stable computation
68Q45: Formal languages and automata
68R10: Graph theory (including graph drawing) in computer science
68M12: Network protocols
Related Items
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
