Fast space optimal leader election in population protocols

MaRDI QIDQ4607897zbMATH OpenFDO

Authors Grzegorz Stachowiak, Leszek Gąsieniec

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1704.07649, http://dl.acm.org/citation.cfm?id=3175286

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)

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

Cited in

(21)

• Simple and Efficient Leader Election
• A survey of size counting in population protocols
• Models of smoothing in dynamic networks
• Running time analysis of broadcast consensus protocols
• Loosely-stabilizing leader election with polylogarithmic convergence time
• Composable computation in discrete chemical reaction networks
• A population protocol for exact majority with \(O(\log^{5/3} n)\) stabilization time and \(\Theta(\log n)\) states
• 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
• scientific article; zbMATH DE number 7651155 (Why is no real title available?)
• scientific article; zbMATH DE number 6850453 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 7561458 (Why is no real title available?)
• 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

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)