2025/08/20 by Attiya, Hagit, Anta, Antonio Fernández, Milani, Alessia +2
#Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2508.14506
Auditability allows to track operations performed on a shared object, recording who accessed which information. This gives data owners more control on their data. Initially studied in the context of single-writer registers, this work extends the notion of auditability to other shared objects, and studies their properties. We start by moving from single-writer to multi-writer registers, and provide an implementation of an auditable n-writer m-reader read / write register, with O(n+m) step complexity. This implementation uses (m+n)-sliding registers, which have consensus number m+n. We show that this consensus number is necessary. The implementation extends naturally to support an auditable load-linked / store-conditional (LL/SC) shared object. LL/SC is a primitive that supports efficient implementation of many shared objects. Finally, we relate auditable registers to other access control objects, by implementing an anti-flickering deny list from auditable registers.