2021/03/22 by Chan, David Y. C., Chi, Shucheng, Hadzilacos, Vassos +1
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2103.11926
In this paper, we first propose a new liveness requirement for shared objects and data structures, we then give a shared queue algorithm that satisfies this requirement and we prove its correctness. We also implement this algorithm and compare it to a well-known shared queue algorithm that is used in practice. In addition to having a stronger worst-case progress guarantee, our experimental results suggest that, at the cost of a marginal decrease in throughput, our algorithm is significantly fairer, by a natural definition of fairness that we introduce here.