Auditable Shared Objects: From Registers to Synchronization Primitives
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916909867335680 |
|---|---|
| author | Attiya, Hagit Anta, Antonio Fernández Milani, Alessia Rapetti, Alexandre Travers, Corentin |
| author_facet | Attiya, Hagit Anta, Antonio Fernández Milani, Alessia Rapetti, Alexandre Travers, Corentin |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_14506 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Auditable Shared Objects: From Registers to Synchronization Primitives Attiya, Hagit Anta, Antonio Fernández Milani, Alessia Rapetti, Alexandre Travers, Corentin Distributed, Parallel, and Cluster Computing Databases Data Structures and Algorithms 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. |
| title | Auditable Shared Objects: From Registers to Synchronization Primitives |
| topic | Distributed, Parallel, and Cluster Computing Databases Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.14506 |