The computational power of simple protocols for self-awareness on graphs

DOI10.1016/J.TCS.2012.08.026MaRDI QIDQ392008zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Ioannis Chatzigiannakis, Othon Michail, Stavros Nikolaou, 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

zbMATH Keywords

complexitygraph propertydiffuse computationfinite-state agentintermittent communicationpassive mobilitypopulation protocolself-awarenessstable computation

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Network protocols (68M12)

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

Cites work

• scientific article; zbMATH DE number 5605125 (Why is no real title available?)
• scientific article; zbMATH DE number 2080936 (Why is no real title available?)
• All symmetric predicates in NSPACE\((n^{2})\) are stably computable by the mediated population protocol model
• Causality, influence, and computation in possibly disconnected synchronous dynamic networks
• Characterizations of classes of graphs recognizable by local computations
• Computation in networks of passively mobile finite-state sensors
• Computation in networks of passively mobile finite-state sensors
• Computational models for networks of tiny artifacts: a survey
• Distributed computation in dynamic networks
• Fast computation by population protocols with a leader
• Mediated Population Protocols
• Mediated population protocols
• Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
• On the convergence of population protocols when population goes to infinity
• Passively mobile communicating machines that use restricted space
• Recent Advances in Population Protocols
• Self-stabilization
• Self-stabilizing systems in spite of distributed control
• Semigroups, Presburger formulas, and languages
• The Dynamics of Probabilistic Population Protocols
• The computational power of population protocols

Cited in

(2)

• Connectivity preserving network transformers
• Connectivity preserving network transformers

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)