Time-space trade-offs in population protocols for the majority problem [0.03%]
多数问题中时间-空间折衷在人口协议中的应用
Petra Berenbrink,Robert Elsässer,Tom Friedetzky et al.
Petra Berenbrink et al.
Population protocols are a model for distributed computing that is focused on simplicity and robustness. A system of n identical agents (finite state machines) performs a global task like electing a unique leader or determining the majority...
Kyrill Winkler,Manfred Schwarz,Ulrich Schmid
Kyrill Winkler
We consider the problem of solving consensus using deterministic algorithms in a synchronous dynamic network with unreliable, directional point-to-point links, which are under the control of a message adversary. In contrast to the large bod...
Benjamin Aminof,Tomer Kotek,Sasha Rubin et al.
Benjamin Aminof et al.
Parameterized model checking is the problem of deciding if a given formula holds irrespective of the number of participating processes. A standard approach for solving the parameterized model checking problem is to reduce it to model checki...
Heinrich Moser,Ulrich Schmid
Heinrich Moser
We present generic transformations, which allow to translate classic fault-tolerant distributed algorithms and their correctness proofs into a real-time distributed computing model (and vice versa). Owing to the non-zero-time, non-preemptib...