BIBLIOS

  Ciências References Management System

Visitor Mode (Login)
Need help?


Back

Publication details

Document type
Conference papers

Document subtype
Extended abstract/Short paper

Title
Brief Announcement: Auditable Register Emulations

Participants in the publication
Vinicius Vielmo Cogo (Author)
Dep. Informática
LASIGE - LASIGE-Computer Science and Engineering Research Centre
Alysson Bessani (Author)
Dep. Informática
LASIGE - LASIGE-Computer Science and Engineering Research Centre

Scope
International

Refereeing
Yes

Summary
We initiate the study of auditable storage emulations, which provide the capability for an auditor to report the previously executed reads in a register. We define the notion of auditable register and its properties, and establish tight bounds and impossibility results for auditable storage emulations in the presence of faulty base storage objects. Our formulation considers registers that securely store data using information dispersal (each base object stores only a block of the written value) and supporting fast reads (that complete in one communication round-trip). In such a scenario, given a maximum number f of faulty storage objects and a minimum number τ of data blocks required to recover a stored value, we prove that (R1) auditability is impossible if τ ≤ 2f; (R2) implementing a weak form of auditability requires τ ≥ 3f + 1; and (R3) a stronger form of auditability is impossible. We also show that (R4) signing read requests generically overcomes the lower bound of weak auditability, while (R5 and R6) totally ordering operations or using non-fast reads enables strong auditability. These results establish that practical storage emulations need f to 2f additional objects compared to their original lower bounds to support auditability.

Editor(s)
Gilbert, Seth

Date of Acceptance
2021-07-23
Date of Publication
2021-10-05

Event
35th International Symposium on Distributed Computing (DISC 2021)

Publication Identifiers
ISSN - 1868-8969
ISBN - 9783959772105

Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Volume
209

Number of pages
4
Starting page
53:1
Last page
53:4

Rankings
CORE A (2021) -


Export

APA
Vinicius Vielmo Cogo, Alysson Bessani, (2021). Brief Announcement: Auditable Register Emulations. 35th International Symposium on Distributed Computing (DISC 2021), 53:1-53:4

IEEE
Vinicius Vielmo Cogo, Alysson Bessani, "Brief Announcement: Auditable Register Emulations" in 35th International Symposium on Distributed Computing (DISC 2021), , 2021, pp. 53:1-53:4, doi:

BIBTEX
@InProceedings{52331, author = {Vinicius Vielmo Cogo and Alysson Bessani}, title = {Brief Announcement: Auditable Register Emulations}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, year = 2021, pages = {53:1-53:4}, address = {}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik} }