Lock-Free Algorithms under Stochastic Schedulers

  • Dan Alistarh ,
  • Thomas Sauerwald ,
  • Milan Vojnovic

MSR-TR-2015-41 |

In this work, we consider the following random process, motivated by the analysis of lock-free concurrent algorithms under stochastic schedulers. In each step, a new ball is allocated into one of $n$ bins, according to a distribution $\vect{p} = (p_1, p_2, \ldots, p_n)$, where each ball goes to bin $i$ with probability $p_i$. When some bin first reaches a set threshold of balls, it registers a \emph{win}, and resets its ball count to $1$. At the same time, bins whose ball count was close to the threshold also get reset on a win, to $0$ balls, being penalized for \emph{almost} winning. We are interested in two questions: how often does \emph{some} bin win (\emph{system latency}), and how often does a \emph{specific} bin win (\emph{individual latency})?

We provide asymptotically tight bounds for the system and individual latency of this general concurrency pattern, for arbitrary scheduling distributions $\vect{p}$. We find that, surprisingly, a simple characterization exists: in expectation, the system will complete a new operation every $\Theta( 1 / \| \vect{p} \|_2 )$ steps, while thread $i$ will complete a new operation every $\Theta( \| \vect{p} \|_2 / p_i^2 )$ steps. The proof of this result is quite involved, as it requires a careful analysis of how the higher norms of the vector $\vect{p}$ influence the occupancy distribution of bins and latencies in this random process. Our result offers a simple relation between the scheduling distribution and the average performance of concurrent algorithms, which has several practical applications.