Wait-Freedom is Harder than Lock-Freedom under Strong Linearizability

Oksana Denysyuk (1) , Philipp Woelfel (1)

1 CPSC - Department of Computer Science [Calgary]

In randomized algorithms, replacing atomic shared objects with linearizable [1] implementations may affect probability distributions over outcomes [2]. To avoid this problem in the adaptive adversary model, it is necessary and sufficient that implemented objects satisfy strong lin-earizability [2]. In this paper we study the existence of strongly lineariz-able implementations from multi-writer registers. We prove the impossibility of wait-free strongly linearizable implementations for a number of standard objects, including snapshots, counters, and max-registers, all of which have wait-free linearizable implementations. To do so, we introduce a new notion of group valency that is useful to analyze (strongly linearizable) implementations from registers. Furthermore, we show that many objects, including snapshots, do have lock-free strongly linearizable implementations. These results separate lock-freedom from wait-freedom under strong linearizability.

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

Oksana Denysyuk, Philipp Woelfel. Wait-Freedom is Harder than Lock-Freedom under Strong Linearizability. DISC 2015, Toshimitsu Masuzawa; Koichi Wada, Oct 2015, Tokyo, Japan. ⟨10.1007/978-3-662-48653-5_5⟩. ⟨hal-01199821⟩