Lock-Free Algorithms under Stochastic Schedulers

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 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 almost winning. We are interested in two questions: how often does some bin win (system latency), and how often does a specific bin win (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.