Upper and Lower Bounds for Deterministic Approximate Objects
Danny Hendler, Adnane Khattabi, Alessia Milani, Corentin Travers · 2021
Relaxing the sequential specification of shared objects has been proposed as a promising approach to obtain implementations with better complexity. In this paper, we study the step complexity of relaxed variants of two common shared objects: max registers and counters. In particular, we consider the$k$-multiplicative-accurate max register and the k-multiplicative-accurate counter, where read operations are allowed to err by a multiplicative factor of$k$(for some$k\in \mathbb{N}$). More accurately, reads are allowed to return an approximate value$x$of the maximum value$v$previously written to the max register, or of the number$v$of increments previously applied to the counter, respectively, such that$v/k\leq x\leq v. k$. We provide upper and lower bounds on the complexity of implementing these objects in a wait-free manner in the shared memory model.