Mediated population protocols

DOI10.1016/J.TCS.2011.02.003MaRDI QIDQ533894zbMATHOpenAlexWikidataFDO

Authors Othon Michail, Ioannis Chatzigiannakis, P. G. Spirakis

Publication date 10 May 2011

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

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

zbMATH Keywords

diffuse computationfinite-state agentintermittent communicationpassive mobilitypopulation protocolstable computation

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Mathematical problems of computer architecture (68M07)

Recommendations

• Mediated Population Protocols
• Recent Advances in Population Protocols
• All symmetric predicates in NSPACE\((n^{2})\) are stably computable by the mediated population protocol model
• The computational power of population protocols
• Population protocols on graphs: a hierarchy

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 5605125 (Why is no real title available?)
• scientific article; zbMATH DE number 4087055 (Why is no real title available?)
• A simple population protocol for fast robust approximate majority
• All symmetric predicates in NSPACE\((n^{2})\) are stably computable by the mediated population protocol model
• 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
• Fast computation by population protocols with a leader
• Mediated Population Protocols
• Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
• Nondeterministic Space is Closed under Complementation
• On the convergence of population protocols when population goes to infinity
• Passively mobile communicating machines that use restricted space
• Playing with population protocols
• Recent Advances in Population Protocols
• Self-stabilizing counting in mobile sensor networks
• Semigroups, Presburger formulas, and languages
• Stably computable predicates are semilinear
• The Dynamics of Probabilistic Population Protocols
• The computational power of population protocols

Cited in

(42)

• Fault tolerant network constructors
• Distributed computation and reconfiguration in actively dynamic networks
• A glimpse at Paul G. Spirakis
• Running time analysis of broadcast consensus protocols
• The Dynamics of Probabilistic Population Protocols
• An introduction to temporal graphs: an algorithmic perspective
• Fault tolerant network constructors
• Simple and fast approximate counting and leader election in populations
• Mediated population protocols: leader election and applications
• Population protocols on graphs: a hierarchy
• Clocked population protocols
• Terminating distributed construction of shapes and patterns in a fair solution of automata
• Network Constructors: A Model for Programmable Matter
• Tight complexity analysis of population protocols with cover times -- the ZebraNet example
• The computational power of simple protocols for self-awareness on graphs
• Large flocks of small birds: on the minimal size of population protocols
• scientific article; zbMATH DE number 7449997 (Why is no real title available?)
• All symmetric predicates in NSPACE\((n^{2})\) are stably computable by the mediated population protocol model
• Traveling salesman problems in temporal graphs
• Population protocols with unreliable communication
• Recent Advances in Population Protocols
• Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication
• The complexity of optimal design of temporally connected graphs
• scientific article; zbMATH DE number 7561256 (Why is no real title available?)
• How Many Cooks Spoil the Soup?
• Space-efficient self-stabilizing counting population protocols on mobile sensor networks
• Protocols with constant local storage and unreliable communication
• Fault-tolerant simulation of population protocols
• Temporal network optimization subject to connectivity constraints
• The complexity of verifying population protocols
• Mediated Population Protocols
• Blockchain in dynamic networks
• Homonym population protocols
• How many cooks spoil the soup?
• Causality, influence, and computation in possibly disconnected synchronous dynamic networks
• On space complexity of self-stabilizing leader election in mediated population protocol
• An introduction to temporal graphs: an algorithmic perspective
• Connectivity preserving network transformers
• Stably computable predicates are semilinear
• Connectivity preserving network transformers
• A Survey on Analog Models of Computation
• Passively mobile communicating machines that use restricted space

This page was built for publication: Mediated population protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q533894)