2017/07/24 by Mauro Ianni, Ianni, Mauro, Alessandro Pellegrini +3
Computer Science · Engineering · #Advanced Memory and Neural Computing #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Parallel #Quantum Computing Algorithms and Architecture #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1707.07478
openalex publication_date 2017/07/24 · openalex created_date 2022/08/16 · openalex updated_date 2026/07/28
We present a multi-word atomic (1,N) register for multi-core machines\nexploiting Read-Modify-Write (RMW) instructions to coordinate the writer and\nthe readers in a wait-free manner. Our proposal, called Anonymous Readers\nCounting (ARC), enables large-scale data sharing by admitting up to 232-2\nconcurrent readers on off-the-shelf 64-bits machines, as opposed to the most\nadvanced RMW-based approach which is limited to 58 readers. Further, ARC avoids\nmultiple copies of the register content when accessing it---this affects\nclassical register's algorithms based on atomic read/write operations on single\nwords. Thus it allows for higher scalability with respect to the register size.\nMoreover, ARC explicitly reduces improves performance via a proper limitation\nof RMW instructions in case of read operations, and by supporting constant time\nfor read operations and amortized constant time for write operations. A proof\nof correctness of our register algorithm is also provided, together with\nexperimental data for a comparison with literature proposals. Beyond assessing\nARC on physical platforms, we carry out as well an experimentation on\nvirtualized infrastructures, which shows the resilience of wait-free\nsynchronization as provided by ARC with respect to CPU-steal times, proper of\nmore modern paradigms such as cloud computing.\n