Outputs (2)

A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states (2018)
Presentation / Conference Contribution
Berenbrink, P., Elsässer, R., Friedetzky, T., Kaaser, D., Kling, P., & Radzik, T. (2018, October). A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states. Presented at International Symposium on DIStributed Computing (DISC), New Orleans, USA

A population protocol is a sequence of pairwise interactions of n agents. During one interaction, two randomly selected agents update their states by applying a deterministic transition function. The goal is to stabilize the system at a desired outpu... Read More about A population protocol for exact majority with $O(\log^{5/3} n)$ stabilization time and asymptotically optimal number of states.

Self-Stabilizing Balls and Bins in Batches (2018)
Journal Article
Berenbrink, P., Friedetzky, T., Kling, P., Mallmann-Trenn, F., Nagel, L., & Wastell, C. (2018). Self-Stabilizing Balls and Bins in Batches. Algorithmica, 80(12), 3673-3703. https://doi.org/10.1007/s00453-018-0411-z

A fundamental problem in distributed computing is the distribution of requests to a set of uniform servers without a centralized controller. Classically, such problems are modeled as static balls into bins processes, where m balls (tasks) are to be d... Read More about Self-Stabilizing Balls and Bins in Batches.