The synchronization power of auditable single-writer registers

Auditability enables tracking of all read operations performed on a register, allowing data owners to monitor access to their data. This paper explores formal models of single-writer auditable registers and examines their feasibility and synchronization requirements.A natural definition of auditable registers, atomic audit requires that all write, read, and audit operations be linearized. We show that atomic auditing is a powerful synchronization primitive, as it can be used to solve consensus. The ability to solve consensus with atomic audit depends on the number of readers and auditors: if there is a single reader or a single auditor (the writer), consensus can be solved among two processes. If there are n readers and n auditors, consensus can be solved among n processes. This result highlights the strong synchronization needed to support atomic auditing.We present wait-free implementations of single-writer atomic registers with atomic audit. For multiple readers and a single auditor, our implementation relies on primitives with consensus number 2 (e.g., swap and fetch&add). When there are n readers and multiple auditors, we introduce an implementation based on (n + 1)-sliding registers, which have consensus number n + 1.Due to the inherent complexity of atomic auditing, we introduce a weaker definition: regular audit, where audit operations are not linearized with reads and writes. We prove that atomic registers with regular audit can be implemented using standard atomic registers, demonstrating that auditability can be achieved with lower synchronization costs in this weaker model.