Uniform bipartition in the population protocol model with arbitrary graphs

DOI10.1016/J.TCS.2021.09.020OpenAlexW3198935539MaRDI QIDQ2235772FDOQ2235772

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)

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

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

zbMATH Keywords

distributed protocolpopulation protocoluniform bipartition

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

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

Cited In (2)

• Constant-space population protocols for uniform bipartition
• Title not available (Why is that?)

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)