Mediated population protocols
From MaRDI portal
Publication:533894
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
diffuse computationfinite-state agentintermittent communicationpassive mobilitypopulation protocolstable computation
Mathematical problems of computer architecture (68M07) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
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
