Fast space optimal leader election in population protocols

zbMATH Open1403.68064arXiv1704.07649MaRDI QIDQ4607897FDOQ4607897

Authors: Grzegorz Stachowiak, Leszek Gąsieniec 

Publication date: 15 March 2018

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

Recommendations

• Enhanced Phase Clocks, Population Protocols, and Fast Space Optimal Leader Election
• Polylogarithmic-time leader election in population protocols
• Brief announcement: Population protocols for leader election and exact majority with \(O(\log^{2} n)\) states and \(O(\log^{2}n)\) convergence time
• scientific article; zbMATH DE number 6850453
• Brief Announcement

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed systems (68M14) Network protocols (68M12)

Cited In (21)

• A survey of size counting in population protocols
• Running time analysis of broadcast consensus protocols
• Loosely-stabilizing leader election with polylogarithmic convergence time
• A population protocol for exact majority with \(O(\log^{5/3} n)\) stabilization time and \(\Theta(\log n)\) states
• Composable computation in discrete chemical reaction networks
• Leader election requires logarithmic time in population protocols
• Simple and fast approximate counting and leader election in populations
• ppsim: a software package for efficiently simulating and visualizing population protocols
• Title not available (Why is that?)
• Title not available (Why is that?)
• Fast computation by population protocols with a leader
• Message complexity of population protocols
• Data collection in population protocols with non-uniformly random scheduler
• Composable computation in leaderless, discrete chemical reaction networks
• Title not available (Why is that?)
• Noidy conmunixatipn: on the convergence of the averaging population protocol
• On convergence and threshold properties of discrete Lotka-Volterra population protocols
• Logarithmic expected-time leader election in population protocol model
• Time-space trade-offs in population protocols for the majority problem
• Simple and Efficient Leader Election
• Models of smoothing in dynamic networks

This page was built for publication: Fast space optimal leader election in population protocols

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