Byzantine Auditable Atomic Register with Optimal Resilience

International audience ; 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 4f+1 servers, where at most f can be Byzantine. We show that 4f+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 3f+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.