5 papers
The Instability of all Backoff Protocols
Leslie Ann Goldberg, John Lapinskas
In this paper we prove Aldous's conjecture from 1987 that there is no backoff protocol that is stable for any positive arrival rate. The setting is a communication channel for coor…
Temporal Conductance and Bounds on the Voter Model for Dynamic Networks
Tatiana Rocha Avila, Holger Dell, John Lapinskas
The voter model is a classical stochastic process that models how opinions might spread through a network: at each step, every node lazily adopts the opinion of a random neighbour;…
Degree-dependent and distance-dependent contact rates interpolate between explosive, exponential and polynomial epidemic growth
Zylan Benjert, Júlia Komjáthy, Johannes Lengler +2
It is a fundamental question in epidemiology to estimate, model and predict the growth rate of a pandemic. Analogously, analysing the diffusion of innovation, (fake) news, memes, a…
Instability of backoff protocols with arbitrary arrival rates
Leslie Ann Goldberg, John Lapinskas
In contention resolution, multiple processors are trying to coordinate to send discrete messages through a shared channel with limited communication. If two processors send at the…
Polynomial growth in degree-dependent first passage percolation on spatial random graphs
Júlia Komjáthy, John Lapinskas, Johannes Lengler +1
In this paper we study a version of (non-Markovian) first passage percolation on graphs, where the transmission time between two connected vertices is non-iid, but increases by a p…