Auditing data accesses helps preserve privacy and ensures accountability by allowing one to determine who accessed (potentially sensitive) information. A prior formal definition of register auditability was based on the values returned by read operations, without accounting for cases where a reader might learn a value without explicitly reading it or gain knowledge of data access without being an auditor.

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.

An auditable register extends the classical register with an audit operation that returns information on the read operations performed on the register. In this paper, we study Byzantine resilient auditable registers implementations in an asynchronous message-passing system. Existing solutions implement the auditable register on top of at least$4\mathrm{f}+1$servers, where at most$f$can be Byzantine. We show that$4\mathrm{f}+1$servers are necessary to implement auditability without communication between servers. Then, we pursue the study by relaxing the constraint on the servers' communication, letting them interact with each other. In this setting, we prove that$3\mathrm{f}+1$servers are sufficient. This result establishes that with communication between servers, auditability does not come with an additional cost in terms of the number of servers.