The computational power of simple protocols for self-awareness on graphs
DOI10.1016/J.TCS.2012.08.026zbMATH Open1358.68034DBLPjournals/tcs/ChatzigiannakisMNS13OpenAlexW2092894787WikidataQ57608028 ScholiaQ57608028MaRDI QIDQ392008FDOQ392008
Ioannis Chatzigiannakis, Stavros Nikolaou, Othon Michail, P. 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
Recommendations
- scientific article; zbMATH DE number 512941
- The computational power of population protocols
- scientific article; zbMATH DE number 2006642
- The complexity of computations by networks
- Publication:4502806
- A note on the relationship between graphs and information protocols
- Non trivial computations in anonymous dynamic networks
- Complexity of Graph Self-assembly in Accretive Systems and Self-destructible Systems
- Complexity of graph self-assembly in accretive systems and self-destructible systems
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)
Cites Work
- Computation in networks of passively mobile finite-state sensors
- Semigroups, Presburger formulas, and languages
- Self-stabilization
- Self-stabilizing systems in spite of distributed control
- The computational power of population protocols
- Fast computation by population protocols with a leader
- Title not available (Why is that?)
- Distributed computation in dynamic networks
- Mediated population protocols
- Causality, influence, and computation in possibly disconnected synchronous dynamic networks
- Title not available (Why is that?)
- On the convergence of population protocols when population goes to infinity
- Characterizations of classes of graphs recognizable by local computations
- 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
- Computational models for networks of tiny artifacts: a survey
- Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
- Computation in networks of passively mobile finite-state sensors
- Passively mobile communicating machines that use restricted space
Cited In (2)
This page was built for publication: The computational power of simple protocols for self-awareness on graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392008)
