A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States

DOI10.4230/LIPICS.DISC.2018.10zbMATH Open1497.68034OpenAlexW2899320093MaRDI QIDQ5090899FDOQ5090899

Dominik Kaaser, Petra Berenbrink, Robert Elsässer, Tomasz Radzik, Tom Friedetzky, Peter Kling

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/lipics.disc.2018.10

zbMATH Keywords

randomized algorithmsmajoritypopulation protocols

Mathematics Subject Classification ID

Randomized algorithms (68W20) Distributed systems (68M14) Network protocols (68M12)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Computation in networks of passively mobile finite-state sensors
• Fast computation by population protocols with a leader
• Fast and exact majority in population protocols
• Determining Majority in Networks with Local Interactions and Very Small Local Memory
• Time-Space Trade-offs in Population Protocols
• A Polylogarithmic Gossip Algorithm for Plurality Consensus
• Brief Announcement
• Plurality consensus in arbitrary graphs : lessons learned from load balancing.

Cited In (8)

• A survey of size counting in population protocols
• Distributed computation with continual population growth
• Uniform bipartition in the population protocol model with arbitrary graphs
• Title not available (Why is that?)
• Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model
• Data collection in population protocols with non-uniformly random scheduler
• On convergence and threshold properties of discrete Lotka-Volterra population protocols
• Time-space trade-offs in population protocols for the majority problem

This page was built for publication: A Population Protocol for Exact Majority with O(log5/3 n) Stabilization Time and Theta(log n) States

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