Why Non-Blocking Operations Should Be Selfish

Joel Gibson (1) , Vincent Gramoli (1, 2)

1 IT - School of Information Technologies [Sydney]
2 NICTA - National ICT Australia [Sydney]

Non-blocking data structures are often analysed by giving an upper amortised running time bound in terms of the size of the data structure and a measure of contention. The two most commonly used measures are the point contention cP , the maximum number of processes active at any one time during an operation, and the interval contention cI , the number of operations overlapping with a given operation. In this paper, we show that when summed across every operation in an exe- cution, the interval contention cI is within a factor of 2 of the point contention cP . Our proof relies on properties of interval graphs where at least one simplicial vertex exists, and uses it to construct a lower bound on the overall point contention. We show that this bound is tight. This result contradicts the folklore belief that point contention leads to a tighter bound on complexity in an amortised context, and provides some theoretical grounds for recent observations that using less helping in non-blocking data structures can lead to better performance. We also propose a linked list algorithm based on Fomitchev and Ruppert’s algorithm but with selfish operations: read-only operations that do not help others but rather execute wait-free. The higher performance of our approach compared to the original list confirms that reducing helping can increase performance, with the same asymptotic amortised complexity.

Keywords: Helping; lock-freedom; wait-freedom; point contention; process contention; interval contention; overlapping-interval contention

Domains: Distributed, Parallel, and Cluster Computing [cs.DC]

Joel Gibson, Vincent Gramoli. Why Non-Blocking Operations Should Be Selfish. DISC 2015, Toshimitsu Masuzawa; Koichi Wada, Oct 2015, Tokyo, Japan. ⟨10.1007/978-3-662-48653-5_14⟩. ⟨hal-01206442⟩