36 citations · 118 across the 28 of their papers we have counts for
6 papers · 1 filter
Threshold Load Balancing in Networks
Martin Hoefer, Thomas Sauerwald
We study probabilistic protocols for concurrent threshold-based load balancing in networks. There are n resources or machines represented by nodes in an undirected graph and m >> n…
Quasirandom Rumor Spreading: An Experimental Analysis
Benjamin Doerr, Tobias Friedrich, Marvin Künnemann +1
We empirically analyze two versions of the well-known "randomized rumor spreading" protocol to disseminate a piece of information in networks. In the classical model, in each round…
Quasirandom Rumor Spreading
Benjamin Doerr, Tobias Friedrich, Thomas Sauerwald
We propose and analyze a quasirandom analogue of the classical push model for disseminating information in networks ("randomized rumor spreading"). In the classical model, in each…
Smoothed Analysis of Balancing Networks
Tobias Friedrich, Thomas Sauerwald, Dan Vilenchik
In a balancing network each processor has an initial collection of unit-size jobs (tokens) and in each round, pairs of processors connected by balancers split their load as evenly…
Quasirandom Load Balancing
Tobias Friedrich, Martin Gairing, Thomas Sauerwald
We propose a simple distributed algorithm for balancing indivisible tokens on graphs. The algorithm is completely deterministic, though it tries to imitate (and enhance) a random a…
Cover Time and Broadcast Time
Robert Elsässer, Thomas Sauerwald
We introduce a new technique for bounding the cover time of random walks by relating it to the runtime of randomized broadcast. In particular, we strongly confirm for dense graphs…