2 papers
cs.DC2026
Near-optimal population protocols on bounded-degree trees
Joel Rybicki, Jakob Solnerzik, Robin Vacus
We investigate space-time trade-offs for population protocols in sparse interaction graphs. In complete interaction graphs, optimal space-time trade-offs are known for the leader e…
cs.DC2025
Space-efficient population protocols for exact majority on general graphs
Joel Rybicki, Jakob Solnerzik, Olivier Stietel +1
We study exact majority consensus in the population protocol model. In this model, the system is described by a graph with nodes, and in each time step, a scheduler…