22 citations · 70 across the 13 of their papers we have counts for
4 papers · 1 filter
Breaking the log n barrier on rumor spreading
Chen Avin, Robert Elsässer
rounds has been a well known upper bound for rumor spreading using push&pull in the random phone call model (i.e., uniform gossip in the complete graph). A matching low…
The Power of Two Choices in Distributed Voting
Colin Cooper, Robert Elsässer, Tomasz Radzik
Distributed voting is a fundamental topic in distributed computing. In pull voting, in each step every vertex chooses a neighbour uniformly at random, and adopts its opinion. The v…
Coalescing random walks and voting on connected graphs
Colin Cooper, Robert Elsasser, Hirotaka Ono +1
In a coalescing random walk, a set of particles make independent random walks on a graph. Whenever one or more particles meet at a vertex, they unite to form a single particle, whi…
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…