2020/06/11 by Vassos Hadzilacos, Xing Hu, Hadzilacos, Vassos +3
Computer Science · Engineering · #Advanced Memory and Neural Computing #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2006.06771
openalex publication_date 2020/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The well-known randomized consensus algorithm by Aspnes and Herlihy for asynchronous shared-memory systems was proved to work, even against a strong adversary, under the assumption that the registers that it uses are atomic registers. With atomic registers, every read or write operation is instantaneous (and thus indivisible). As pointed out by Golab et al. (2011), however, a randomized algorithm that works with atomic registers does not necessarily work if we replace the atomic registers that it uses with linearizable implementations of registers. This raises the following question: does the randomized consensus algorithm by Aspnes and Herlihy still work against a strong adversary if we replace its atomic registers with linearizable registers? We show that the answer is affirmative, in fact, we show that even linearizable registers are not necessary. More precisely, we prove that the algorithm by Aspnes and Herlihy works against a strong adversary even if the algorithm uses only regular registers.