Auditable Shared Objects: From Registers to Synchronization Primitives

Auditability was introduced by Cogo and Bessani [8] in the context of replicated registers. They considered a register as an abstraction for distributed storage that provides read and write operations to clients. Cogo and Bessani define auditability in terms of two properties: completeness ensures that all readers’ data access are detected, while accuracy ensures that readers who do not access data are not wrongly incriminated. They present an algorithm to implement an auditable regular (non-atomic) register, using $n\ge 4f+1$ atomic read/write shared objects, $f$ of which may be faulty (writers and auditors fail only by crashing; faulty readers may be Byzantine). Their implementation relies on information dispersal schemes, where the input of a high-level write is split into several pieces, each written in a different low-level shared object. Each low-level shared object keeps a trace of each access, and in order to read, a process has to collect sufficiently many pieces of information in many low-level shared objects, which allows to audit the read.

In asynchronous message-passing systems where $f$ processes can be Byzantine, Del Pozzo, Milani, and Rapetti [9] study the possibility of implementing an atomic auditable register. They prove that without communication between servers, auditability requires at least $4f+1$ servers. They also show that allowing servers to communicate with each other admits an auditable atomic register with optimal resilience of $3f+1$.

The auditability definition of [8] is tightly coupled with their multi-writer, multi-reader register emulation in a replicated storage system using an information-dispersal scheme. An implementation-agnostic auditability definition was later proposed by Attiya et al. [6], based on collectively linearizing read, write, and audit operations. They show that auditing adds power to reading and writing, as it allows to solve consensus, implying that auditing requires strong synchronization primitives. They also give several implementations that use non-universal primitives (like swap and fetch&add), for a single writer and either several readers or several auditors (but not both).

Recent work [4] have extended auditability to ensure that even a curious (but honest) reader cannot effectively read data without being audited; in fact, curious readers cannot even audit other readers. The paper provides implementations of several auditable objects, including registers. However, the constructions depend on universal primitives, including compare&swap, in contrast to our constructions, which only employ sliding registers, whose consensus number is bounded.

Alhajaili and Jhumka [1] study an interesting variant of auditability with malicious processes, with and without a trusted party. Their definition of auditability has to do with the ability of determining if a system runs as specified, and determine the incorrect behavior in case it does not. This involves systematically tracking and recording system activities to facilitate fault detection and diagnosis. The authors propose methodologies for integrating auditability into system design, emphasizing its role in simplifying the debugging process and improving overall system robustness.

Our algorithms (like most prior work) maintain a large amount of auditing information, which grows with the number of operations performed in an execution. Hajisheykhi, Roohitavaf, and Kulkarni [13] investigate how to reduce the space used for saving auditing data (to be used to restore the state after a fault), by leveraging causal dependencies among them. They propose protocols for ensuring accountability in distributed systems when auditable events – deviations from standard protocols – occur. They introduce two self-stabilizing protocols: an unbounded state space protocol that propagates auditable events across all nodes and a more efficient bounded state space protocol that achieves the same awareness without increasing resource demands. Their approach ensures that before a system can recover from an auditable event, all processes are aware of it, preventing unauthorized restorations and reinforcing accountability.

Access control objects regulate access to resources by defining policies for granting or denying permissions. Some of the most common access control mechanisms include Access Control Lists [21], which specify allowed or denied actions for individual users or processes, and Capability-Based Access Control [18], where access is granted through transferable tokens rather than predefined rules. Role-Based Access Control [20] simplifies management by assigning permissions to roles instead of individuals, making it widely used in enterprise environments, while Attribute-Based Access Control [15] dynamically evaluate attributes such as user location, device type, and time of access. AllowLists and DenyLists [11] further control access by explicitly specifying permitted or blocked users or processes, often used in security filters and authentication systems.

An area related to auditability is data provenance (also called lineage) in databases [7, 12], which involves tracking the origin and transformations of data, focusing on its lineage across different processes or systems. Provenance is concerned with the integrity, quality, and reproducibility of data as it moves through various stages, such as aggregation or computation. While both auditability and provenance track interactions with data, auditability is more focused on recording who performed an operation, primarily for access control and security, while provenance aims to provide transparency about the history and transformations of the data for purposes such as verification and accountability in data analysis.

• $\mathrm{■}$

  We extend auditability from single-writer to multi-writer registers and characterize the necessary and sufficient consensus number needed for their implementation.

• $\mathrm{■}$

  We introduce and implement auditable LL/SC objects, demonstrating auditability can be provided beyond read / write operations.

• $\mathrm{■}$

  We construct an anti-flickering Deny List object from auditable registers, illustrating the connection between auditability and access control mechanisms.

Section 2 presents our model and formally defines auditable shared objects. Sections 3 and 4 prove the necessary and sufficient conditions for auditable multi-writer registers, respectively. Section 5 describes how to implement auditable LL/SC objects. Section 6 presents the algorithm to implement an anti-flickering Deny List object with auditable registers. Finally, Section 7 concludes with open questions and future directions. Proofs omitted due to space constraints can be found in the full version [5].

An implementation of an auditable register has to keep track of the latest value written to the register as well as, for each written value, its set of readers. This can be easily achieved using a single sliding register $\mathrm{𝑆𝐿𝑅}$, provided that its window is unbounded. Such a register hence stores the complete sequence of values written to it, ordered by the oldest first but has infinite consensus number. To perform a write($v$), a writer simply writes $v$ to $\mathrm{𝑆𝐿𝑅}$. For auditing purpose, a reader $p_i$ first writes its identifier $i$ to the sliding register, before reading it. The value returned by this read is then the nearest non-identifier value in the sequence read from $\mathrm{𝑆𝐿𝑅}$ previous to the identifier $i$ written by $p_i$. The reader set of each value can easily be inferred from the sequence stored in $\mathrm{𝑆𝐿𝑅}$. For a value $v$ in the sequence, its reader set is the set of processes whose identifiers follows $v$, and are before the first non-identifier value that succeeds $v$, if any.

Our implementation (Algorithms 1 and 2) is based on this simple idea, but instead of a single sliding register with an unbounded window, we use an unbounded array $SLR[-1,\mathrm{\dots }]$ of sliding registers, each with a bounded window of size $m+n$. In order not to confuse identifiers and written values, write operations insert into the sliding registers $w$-tuples of the form $(𝗐,j,v,h)$, where $j$ the identifier of the writer, $v$ is the input value of the write operation, and $h$ a helping set of readers’ identifiers (whose role will be explained later).

Each sliding register $\mathrm{𝑆𝐿𝑅}[x]$ contains initially the empty sequence $()$, except the first $\mathrm{𝑆𝐿𝑅}[-1]$ whose sequence contains the $w$-tuple $(𝗐,j_0,v_0,\mathrm{\varnothing })$ where $v_0$ is the initial value of the auditable register and $j_0$ an arbitrary writer’s identifier. At any point in the execution, the current value $v$ of the auditable register is found in the sliding register with highest index $x$ whose sequence contains a $w$-tuple. Specifically, $v$ is the value contained in the first $w$-tuple in the sequence stored in $\text{<em class="ltx\_emph ltx\_font\_italic">SLR</em>}[x]$. Similarly to the basic implementation sketched above, readers of this value (if any) are the processes whose identifiers appear before any $w$-tuple in the next sliding register $\text{<em class="ltx\_emph ltx\_font\_italic">SLR</em>}[x+1]$.

Therefore, reading or writing the auditable register involves finding the valid sliding register (that is, one that does not contain a $w$-tuple) with lowest index. If this is not done with care, progress of some operation may be lost. For example, the same writer may be always the first to write in each sliding register (i.e., each non empty sequence in any sliding register starts with a $w$-tuple posted by this writer), thus preventing read operations from completing or other writers from changing the value of the auditable register. We also have to make sure that each writer or reader writes at most once to each sliding register. Otherwise, the auditing may become inaccurate (as readers identifiers may be removed from some sequence), or the current value of the auditable register may be lost.

To solve theses challenges, the implementation combines the following ideas:

First, we observe that a write operation can terminate after writing in a given sliding register $\mathrm{𝑆𝐿𝑅}[x]$, even if its corresponding $w$-tuple is not the first in the sequence held in $\mathrm{𝑆𝐿𝑅}[x]$, provided that that it is concurrent with the write operation that writes first its $w$-tuple into $SLR[x]$. Indeed, in that case, the write operations that are late to post their $w$-tuple may be linearized immediately before the write whose $w$-tuple is first. Accordingly, the value, denoted $v_x$, in the first $w$-tuple in the sequence stored in $SLR[x]$ is said to be visible. The values in the other $w$-tuple are never returned by any read operation, and are thus invisible.

Second, we use a max register $M$ to store the current smallest index $widx$ of the still valid sliding registers. Recall that a max register retains the largest value written to it; wait-free and linearizable max registers can be implemented from atomic read/write registers with linear step complexity [3]. A write thus starts by retrieving this index from $M$, writes its $w$-tuple in $SLR[widx]$, and finally updates $M$ with the new index $widx+1$. This ensures that, if several write operations post $w$-tuples in the same sliding register $SLR[x]$, they are concurrent.

In addition, $M$ stores an $m$-vector $ridx$ of indexes of sliding registers (which is part of the helping mechanism described next) and, for convenience, the $auditset$ of the values written whose set of readers is already completely determined (the set of readers of each visible value $v_x$, for ). Triples $(widx,ridx,auditset)$ are ordered by their first field. An audit operation therefore reads $M$, and for $M.widx=x$, gets the definitive readers of values $v_{x^{\prime }},x^{\prime }\le x-2$ from $M.auditset$, to which it adds the possibly non-definitive set of readers of $v_{x-1}$ by reading $SLR[x]$.

Finally, a helping mechanism is used to make sure that read operations are wait-free. The set of readers of the visible value $v_x$ (that appears in the first $w$-tuple stored in $SLR[x]$) are the processes whose identifiers are before any $w$-tuple in $SLR[x+1]$ or are in the helping set $h$ of the first $w$-tuple of $SLR[x+1]$. An additional array $H$ indicates, for each reader, the index of the latest sliding register in which it attempted to write its identifier before any $w$-tuple. The array $ridx$ (stored, as seen above, in the max register $M$), records for each reader the highest index of a sliding register in which it has received help (that is, the identifier of the reader is included in the helping set of the first $w$-tuple of that sliding register). A writer $p_j$ hence determines if a given reader $p_i$ needs help by comparing $H[i]$ and $M.ridx[i]$. If , $p_i$ has an ongoing read operation, and $i$ is therefore added to the helping set of the $w$-tuple of the writer. Similarly, reader $p_i$ discovers if it has received help by comparing $M.ridx[i]$ with the index of the latest sliding register in which it writes its identifier.

Hence, besides $w$-tuples, a given sliding register $SLR[x]$ may also include identifiers $i$ of readers, with the following meaning:

1. 1.

   If $i$ appears before the first $w$-tuple in $SLR[x]$, then $p_i$’s read returns $v_{x-1}$, which is the value stored in the first $w$-tuple in $SLR[x-1]$.

2. 2.

   If $i$ appears in the helping set of the first $w$-tuple in $SLR[x]$, then $p_i$’s read also returns $v_{x-1}$ as in the previous case.

3. 3.

   If $i$ appears after the first $w$-tuple, then it is too late and fails to read $v_{x-1}$.

The reader processes satisfying Cases (1) and (2) are said to be recorded in $SLR[x]$. The function readers in Algorithm 2 returns the ids of readers recorded in a sliding register (which is used, in particular, to update the audit set). The processes satisfying Case (2) are called helped in $SLR[x]$.

Regarding Case (3), we prove that after at most two failed attempts, a reader $p_i$ receives help, or succeeds in appearing before any $w$-tuple in a sliding register. The algorithm also ensures that a read operation is helped at most once. Before an attempt to write its id into $SLR[x]$, reader $p_i$ knows, by checking if $ridx[i]\ge H[i]$, if it has already received help. If this is the case, it directly returns the corresponding value without updating $H[i]$.

In this section, we prove Theorem 3, starting with basic properties. We show that each operation returns within $O(m+n)$ of its own steps, and then explain how to construct a sequential execution $\lambda$ that contains all completed operations in an execution $\alpha$, and some pending operations. Lemma 13 shows that $\lambda$ preserves the real-time order between operations in $\alpha$. By Lemma 14, Lemma 15, and Lemma 16, $\lambda$ is a sequential execution of a $m$-reader, $n$-writer auditable register.

To proceed with the detailed proofs, fix a finite execution $\alpha$ of the algorithm. We start with some basic properties. Lemma 4, whose proof is in the full version, shows that that each sliding register retains the complete history of the $\mathrm{𝗐𝗋𝗂𝗍𝖾}$s applied to it.

The max register $M$ stores a triple $(widx,ridx,auditset)$, where $ridx$ is a $m$-vector and $audiset$ a set of (process,value) pairs. Triples are ordered in increasing order of their first element. At any point in the execution, the triple stored in $M$ is thus a triple with the largest first member written to $M$. We also partially order $m$-vectors as follows: $ridx\le rid{x}^{\prime }$ if and only $\forall i\in \{1,\mathrm{\dots },m\},ridx[i]\le rid{x}^{\prime }[i]$.

In the full version, we prove the following lemma by induction on $k$.

By Proposition 5, the successive values of $M.widx$ are $0,1,\mathrm{\dots }$ By Lemma 6(1), $M.ridx$ remains the same while $M.widx$ does not change. Lemma 6(2) implies that the successive vectors in $M.ridx$ are ordered and form an increasing sequence.

Let $\mathrm{𝑊𝐼𝐷𝑋}$ denote the highest index of a sliding register to which a $w$-tuple has been written. That is, at the end of a finite execution $\alpha$, $\mathrm{𝑊𝐼𝐷𝑋}=k$ if and only a $w$-tuple was written in $SLR[k]$, and no $w$-tuple was written in $SLR[k^{\prime }]$, for any $k^{\prime }>k$. When $\mathrm{𝑊𝐼𝐷𝑋}$ is changed to $k+1$ as a result of some process $p$ applying $\mathrm{𝗐𝗋𝗂𝗍𝖾}(𝗐,\mathrm{\_},\mathrm{\_},\mathrm{\_})$ to $SLR[k+1]$, $M.widx\ge k+1$. Indeed, before writing a $w$-tuple to $SLR[k+1]$, $p$ has read $k$ from $M.widx$ in line 30. Observe also that when $M.widx$ is changed from $k$ to $k+1$ by some process $p$, $M.widx\ge k$. Indeed, before applying $M.\mathrm{𝗐𝗋𝗂𝗍𝖾𝖬𝖺𝗑}(k+1,\mathrm{\_},\mathrm{\_})$, $p$ reads a sequence from $SLR[k]$ that contains a $w$-tuple (line 11 or line 22, $p$ is performing a read), or has written a $w$-tuple to $SLR[k]$ (line 35, $p$ is performing a write). This implies that $M.widx$ is always in $\{\mathrm{𝑊𝐼𝐷𝑋},\mathrm{𝑊𝐼𝐷𝑋}-1\}$, which shows:

Combining these observations with Lemma 6(2), we have:

Therefore, the first step that writes a $w$-tuple to $SLR[x]$ is preceded by steps ${\rho }_0,\mathrm{\dots },{\rho }_{x-1}$ that write $w$-tuples to $SLR[0],\mathrm{\dots },SLR[x-1]$, and they are never deleted (by Lemma 4).

Let $x_0$ be the value of the local variable $lsr$ when read operation $op$ by process $p_i$ starts.

If $op$ does not terminate in the $k$th iteration of the loop (line 20), after reading $(x_k,\mathrm{\_},\mathrm{\_})$ from $M$, then $x_k$ is written to $H[i]$ (line 21) before an attempt is made to place $i$ ahead of any $w$-tuple in $SLR[x_k]$. In the full version, we further prove:

Finally, we prove, in the full version, that $op$ does not find help in $SLR[x]$, for any .

An audit operation reads $M$ once and a single sliding register. A write operation applies a single $\mathrm{𝗐𝗋𝗂𝗍𝖾𝖬𝖺𝗑}$ and a single $\mathrm{𝗋𝖾𝖺𝖽}$ to $M$, reads $O(m)$ registers and writes $O(1)$ registers. Since there is a linearizable implementation of max registers for $(m+n)$ processes using registers with $O(m+n)$ step complexity per operation [3], this implies that the step complexity of a write or a audit operation is in $O(m+n)$.

Lemma 20 (Appendix A) shows that read operations are also wait-free, by proving that the repeat loop has at most 3 iterations. This is because a writer may place a $w$-tuple in at most one sliding register without detecting a concurrent read operation and helping it.

To prove linearizability, let $H$ be the history of read, write and audit operations in the execution $\alpha$. For simplicity, we assume that the values written to the register in $\alpha$ are unique. We start by classifying the operations in $H$. Each classified operation $op$ is also associated with an integer $idx(op)$, which is the index of a sliding register.

For read, we distinguish silent, direct and helped operations. Let $op$ be a read operation by some process $p_i$. We denote by $x_0$ the value the local variable $lsr$ when $op$ starts.

• $\mathrm{■}$

  $rop$ is silent if it is not the first read operation by $p_i$ and it immediately returns after reading $SLR[x_0]$ (line 12). This corresponds to the case in which no new write operation has occurred since the last read by $p_i$. We set $idx(op)=x_0$.

If there is no $x>x_0$ for which $i\in \text{readers}(\mathrm{𝑆𝐿𝑅}[x])$, $op$ is unclassified. In that case, note that $op$ has no response in $H$. Otherwise, let $x_1>x_0$ be the smallest index such that $i\in$readers$(\mathrm{𝑆𝐿𝑅}[x_1])$. We set $idx(op)=x_1$ and say that

• $\mathrm{■}$

  $op$ is direct if $i$ precedes any $w$-tuple in $SLR[x_1]$, and helped otherwise, as in that case, $i$ appears in the helping set of the first $w$-tuple in $SLR[x_1]$.

A write($v$) operation $op$ by some process $p_j$ applies at most one write to a sliding register (line 35). $op$ is unclassified if does not write to a sliding register. Otherwise, let $x$ be the index of the sliding register $op$ writes to. $x=idx(op)$ and we say that

• $\mathrm{■}$

  $op$ is visible if $(𝗐,j,v,\mathrm{\_})$ is the first $w$-tuple written to $SLR[x_1]$, and hidden otherwise.

For audit, only operations that have a response in $H$ are classified. Let $op$ be an audit operation that terminates. We define $idx(op)=x$, where $x$ is the value read from $M.widx$ in the first step of $op$ (line 40). $op$ is non-definitive if there is no $w$-tuple in the sequence it reads from $SLR[x]$ (in line 41), and definitive otherwise. Indeed, once a $w$-tuple has been written to $SLR[x]$, the set of readers of $v_{x-1}$ no longer changes, while read operations may still return $v_{x-1}$ after $op$ terminates otherwise ($v_{x-1}$ the value in the first $w$-tuple in $SLR[x-1]$.). In Appendix A, we prove:

We define $H^{\prime }$ that contains every completed operation of $H$ as well as some incomplete operations, to which we add a matching response. We first discard from $H$ every audit and every silent read invocation without a matching response, as well as every invocation of an unclassified read and write operation. We then add at the end a response for each remaining read and write operation that has no response in $H$. The return value of a read operation $op$ with $idx(op)=x$ is the value $val$ in the first $w$-tuple in $(𝗐,\mathrm{\_},val,\mathrm{\_})$ in $SLR[x-1]$. Responses are added in arbitrary order.

A linearization $\lambda (\alpha )$ of $\alpha$ is defined in two steps. We first order operations in $H^{\prime }$ according to their associated index, in ascending order (rule $R0$). We then order operations with the same index. Let $B(x)$ be the set of operations $op\in H^{\prime }$ such that $idx(op)=x$. These operations are ordered according to the following rules.

1. R1

   We place first silent read, direct read and non-definitive audit operations. They are ordered according to the order in which they apply a read (for silent read and non-definitive audit) or a write (for direct read) to $SLR[x]$ in $\alpha$.

2. R2

   We then place helped read in arbitrary order, followed by the definitive audit operations. The definitive audit are ordered according to the order in which they apply a read to $SLR[x]$ in $\alpha$.

3. R3

   We next put every hidden write. They are ordered according to the order in which their write to $SLR[x]$ is applied in $\alpha$.

4. R4

   The (unique) visible write is placed last.

Let $\lambda$ be the linearization obtained by applying linearization rules $R0$-$R4$ to the operations in $H^{\prime }$. In Appendix A, we prove:

Finally, we prove (in Appendix A) that a pair $(p,v)$ is in the set returned by an audit operation $op$ if and only if there is a read by $p$ returning $v$ precedes $op$.