Uniform bipartition in the population protocol model with arbitrary graphs

DOI10.1016/J.TCS.2021.09.020MaRDI QIDQ2235772zbMATH OpenOpenAlexFDO

Authors Hiroto Yasumi, Fukuhito Ooshita, Michiko Inoue, Sébastien Tixeuil

Publication date 21 October 2021

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2011.08366

zbMATH Keywords

distributed protocolpopulation protocoluniform bipartition

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Constant-space population protocols for uniform bipartition
• Time-space trade-offs in population protocols for the majority problem
• Recent results in population protocols for exact majority and leader election
• Brief announcement: Space-optimal naming in population protocols
• Space-optimal proportion consensus with population protocols

Cites work

• scientific article; zbMATH DE number 6850453 (Why is no real title available?)
• A population protocol for exact majority with \(O(\log^{5/3} n)\) stabilization time and \(\Theta(\log n)\) states
• A simple population protocol for fast robust approximate majority
• AnO(log^3/2n) Parallel Time Population Protocol for Majority withO(logn) States
• Brief Announcement
• Computation in networks of passively mobile finite-state sensors
• Constant-space population protocols for uniform bipartition
• Determining majority in networks with local interactions and very small local memory
• Deterministic population protocols for exact majority and plurality
• On Counting the Population Size
• Optimal time and space leader election in population protocols
• Polylogarithmic-time leader election in population protocols
• Realization of periodic functions by self-stabilizing population protocols with synchronous handshakes
• Self-stabilizing Counting in Mobile Sensor Networks with a Base Station
• Space-efficient self-stabilizing counting population protocols on mobile sensor networks
• Space-optimal counting in population protocols
• Time and space optimal counting in population protocols
• Time-space trade-offs in population protocols

Cited in

(2)

• Constant-space population protocols for uniform bipartition
• scientific article; zbMATH DE number 7650858 (Why is no real title available?)

This page was built for publication: Uniform bipartition in the population protocol model with arbitrary graphs

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