Mediated population protocols

DOI10.1016/j.tcs.2011.02.003zbMath1218.68082OpenAlexW2105431882WikidataQ57608051 ScholiaQ57608051MaRDI QIDQ533894

Othon Michail, Ioannis Chatzigiannakis, Paul 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

Related Items (38)

Distributed computation and reconfiguration in actively dynamic networks ⋮ Traveling salesman problems in temporal graphs ⋮ Population protocols with faulty interactions: the impact of a leader ⋮ Simple and fast approximate counting and leader election in populations ⋮ Unnamed Item ⋮ Population protocols with unreliable communication ⋮ A Glimpse at Paul G. Spirakis ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective ⋮ Terminating distributed construction of shapes and patterns in a fair solution of automata ⋮ The complexity of optimal design of temporally connected graphs ⋮ Tight complexity analysis of population protocols with cover times -- the ZebraNet example ⋮ The computational power of simple protocols for self-awareness on graphs ⋮ Fault tolerant network constructors ⋮ Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication ⋮ On space complexity of self-stabilizing leader election in mediated population protocol ⋮ Causality, influence, and computation in possibly disconnected synchronous dynamic networks ⋮ Blockchain in dynamic networks ⋮ Network Constructors: A Model for Programmable Matter ⋮ Protocols with constant local storage and unreliable communication ⋮ Unnamed Item ⋮ Passively mobile communicating machines that use restricted space ⋮ Fault-tolerant simulation of population protocols ⋮ Mediated Population Protocols: Leader Election and Applications ⋮ Running time analysis of broadcast consensus protocols ⋮ Temporal network optimization subject to connectivity constraints ⋮ Connectivity preserving network transformers ⋮ Unnamed Item ⋮ The complexity of verifying population protocols ⋮ Connectivity Preserving Network Transformers ⋮ Simple and efficient local codes for distributed stable network construction ⋮ Clocked population protocols ⋮ Dynamic networks of finite state machines ⋮ Space-efficient self-stabilizing counting population protocols on mobile sensor networks ⋮ Towards efficient verification of population protocols ⋮ How Many Cooks Spoil the Soup? ⋮ How many cooks spoil the soup? ⋮ An Introduction to Temporal Graphs: An Algorithmic Perspective^* ⋮ A Survey on Analog Models of Computation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple population protocol for fast robust approximate majority
• Computational models for networks of tiny artifacts: a survey
• Passively mobile communicating machines that use restricted space
• On the convergence of population protocols when population goes to infinity
• 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
• 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
• Nondeterministic Space is Closed under Complementation
• Stably computable predicates are semilinear
• Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures
• Self-stabilizing counting in mobile sensor networks
• Computation in networks of passively mobile finite-state sensors

This page was built for publication: Mediated population protocols