Dynamic size counting in the population protocol model

DOI10.1145/3662158.3662825MaRDI QIDQ6971985zbMATH OpenFDO

Authors Dominik Kaaser, Maximilian Lohmann

Publication date 13 June 2025

Full work available at URL https://doi.org/10.1145/3662158.3662825

zbMATH Keywords

loose stabilizationphase clockspopulation protocolssize counting

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Cites work

• A population protocol for exact majority with \(O(\log^{5/3} n)\) stabilization time and \(\Theta(\log n)\) states
• A portable high-quality random number generator for lattice field theory simulations
• A survey of size counting in population protocols
• A time and space optimal stable population protocol solving exact majority
• Brief announcement: Population protocols for leader election and exact majority with \(O(\log^{2} n)\) states and \(O(\log^{2}n)\) convergence time
• Computation in networks of passively mobile finite-state sensors
• Computation with finite stochastic chemical reaction networks
• Dynamic size counting in the population protocol model
• Efficient Size Estimation and Impossibility of Termination in Uniform Dense Population Protocols
• Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election
• Fast computation by population protocols with a leader
• Fast consensus via the unconstrained undecided state dynamics
• Fast space optimal leader election in population protocols
• scientific article; zbMATH DE number 6850453 (Why is no real title available?)
• scientific article; zbMATH DE number 3892344 (Why is no real title available?)
• scientific article; zbMATH DE number 7651155 (Why is no real title available?)
• scientific article; zbMATH DE number 7774291 (Why is no real title available?)
• Logarithmic Expected-Time Leader Election in Population Protocol Model
• Loosely-stabilizing leader election in a population protocol model
• On Counting the Population Size
• Optimal time and space leader election in population protocols
• Population Protocols for Exact Plurality Consensus
• ppsim: a software package for efficiently simulating and visualizing population protocols
• Robust detection in leak-prone population protocols
• Self-stabilizing clock synchronization in the presence of Byzantine faults
• Simple and Efficient Leader Election
• Time-space trade-offs in population protocols
• Time-space trade-offs in population protocols for the majority problem

Cited in

(1)

• Dynamic size counting in the population protocol model

This page was built for publication: Dynamic size counting in the population protocol model

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