6 papers
Round and Resilience-Optimal Approximate Agreement on Trees and Block Graphs
Marc Fuchs, Diana Ghinea, Zahra Parsaeian +1
Approximate Agreement () is a fundamental primitive that, even in the presence of Byzantine faults, allows honest parties to obtain close (but not necessarily identic…
Solvability of Approximate Agreement on Graphs and Simplicial Complexes
Joel Rybicki, Yaroslav Verbitsky
Approximate agreement tasks on graphs are discrete relaxations of consensus, where each process in a distributed system is given as input a vertex on a graph , and processes hav…
Reaching Agreement in Competitive Microbial Systems
Victoria Andaur, Janna Burman, Matthias Függer +4
We study distributed agreement in microbial distributed systems under stochastic population dynamics and competitive interactions. Motivated by recent applications in synthetic bio…
What can be computed in average anonymous networks?
Joel Rybicki, Oleg Verbitsky, Maksim Zhukovskii
We study what deterministic distributed algorithms can compute on random input graphs in extremely weak models of distributed computing: all nodes are anonymous, and in each commun…
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…
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…