Bounded wait-free implementation of optimally resilient byzantine storage without (unproven) cryptographic assumptions

Amitanand S. Aiyer; Lorenzo Alvisi; Rida Bazzi

doi:10.1007/978-3-540-75142-7_4

Bounded wait-free implementation of optimally resilient byzantine storage without (unproven) cryptographic assumptions

Amitanand S. Aiyer, Lorenzo Alvisi, Rida Bazzi

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

16 Scopus citations

Abstract

We present the first optimally resilient, bounded, wait-free implementation of a distributed atomic register, tolerating Byzantine readers and (up to one-third of) Byzantine servers, without the use of unproven cryptographic primitives or requiring communication among servers. Unlike previous (non-optimal) solutions, the sizes of messages sent to writers depend only on the actual number of active readers and not on the total number of readers in the system. With a novel use of secret sharing techniques combined with write back throttling we present the first solution to tolerate Byzantine readers information theoretically, without the use of cryptographic techniques based on unproven number-theoretic assumptions.

Original language	English (US)
Title of host publication	Distributed Computing - 21st International Symposium, DISC 2007, Proceedings
Publisher	Springer Verlag
Pages	7-19
Number of pages	13
ISBN (Print)	9783540751410
DOIs	https://doi.org/10.1007/978-3-540-75142-7_4
State	Published - 2007
Event	21st International Symposium on Distributed Computing, DISC 2007 - Lemesos, Cyprus Duration: Sep 24 2007 → Sep 26 2007

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	4731 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	21st International Symposium on Distributed Computing, DISC 2007
Country/Territory	Cyprus
City	Lemesos
Period	9/24/07 → 9/26/07

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-540-75142-7_4

Cite this

Aiyer, A. S., Alvisi, L., & Bazzi, R. (2007). Bounded wait-free implementation of optimally resilient byzantine storage without (unproven) cryptographic assumptions. In Distributed Computing - 21st International Symposium, DISC 2007, Proceedings (pp. 7-19). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4731 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-75142-7_4

Bounded wait-free implementation of optimally resilient byzantine storage without (unproven) cryptographic assumptions. / Aiyer, Amitanand S.; Alvisi, Lorenzo; Bazzi, Rida.
Distributed Computing - 21st International Symposium, DISC 2007, Proceedings. Springer Verlag, 2007. p. 7-19 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4731 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Aiyer, AS, Alvisi, L & Bazzi, R 2007, Bounded wait-free implementation of optimally resilient byzantine storage without (unproven) cryptographic assumptions. in Distributed Computing - 21st International Symposium, DISC 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4731 LNCS, Springer Verlag, pp. 7-19, 21st International Symposium on Distributed Computing, DISC 2007, Lemesos, Cyprus, 9/24/07. https://doi.org/10.1007/978-3-540-75142-7_4

Aiyer AS, Alvisi L, Bazzi R. Bounded wait-free implementation of optimally resilient byzantine storage without (unproven) cryptographic assumptions. In Distributed Computing - 21st International Symposium, DISC 2007, Proceedings. Springer Verlag. 2007. p. 7-19. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-75142-7_4

Aiyer, Amitanand S. ; Alvisi, Lorenzo ; Bazzi, Rida. / Bounded wait-free implementation of optimally resilient byzantine storage without (unproven) cryptographic assumptions. Distributed Computing - 21st International Symposium, DISC 2007, Proceedings. Springer Verlag, 2007. pp. 7-19 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{bf643b5dfd6440d1a716b77f3e09e786,

title = "Bounded wait-free implementation of optimally resilient byzantine storage without (unproven) cryptographic assumptions",

abstract = "We present the first optimally resilient, bounded, wait-free implementation of a distributed atomic register, tolerating Byzantine readers and (up to one-third of) Byzantine servers, without the use of unproven cryptographic primitives or requiring communication among servers. Unlike previous (non-optimal) solutions, the sizes of messages sent to writers depend only on the actual number of active readers and not on the total number of readers in the system. With a novel use of secret sharing techniques combined with write back throttling we present the first solution to tolerate Byzantine readers information theoretically, without the use of cryptographic techniques based on unproven number-theoretic assumptions.",

author = "Aiyer, {Amitanand S.} and Lorenzo Alvisi and Rida Bazzi",

year = "2007",

doi = "10.1007/978-3-540-75142-7_4",

language = "English (US)",

isbn = "9783540751410",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "7--19",

booktitle = "Distributed Computing - 21st International Symposium, DISC 2007, Proceedings",

note = "21st International Symposium on Distributed Computing, DISC 2007 ; Conference date: 24-09-2007 Through 26-09-2007",

}

TY - GEN

T1 - Bounded wait-free implementation of optimally resilient byzantine storage without (unproven) cryptographic assumptions

AU - Aiyer, Amitanand S.

AU - Alvisi, Lorenzo

AU - Bazzi, Rida

PY - 2007

Y1 - 2007

N2 - We present the first optimally resilient, bounded, wait-free implementation of a distributed atomic register, tolerating Byzantine readers and (up to one-third of) Byzantine servers, without the use of unproven cryptographic primitives or requiring communication among servers. Unlike previous (non-optimal) solutions, the sizes of messages sent to writers depend only on the actual number of active readers and not on the total number of readers in the system. With a novel use of secret sharing techniques combined with write back throttling we present the first solution to tolerate Byzantine readers information theoretically, without the use of cryptographic techniques based on unproven number-theoretic assumptions.

AB - We present the first optimally resilient, bounded, wait-free implementation of a distributed atomic register, tolerating Byzantine readers and (up to one-third of) Byzantine servers, without the use of unproven cryptographic primitives or requiring communication among servers. Unlike previous (non-optimal) solutions, the sizes of messages sent to writers depend only on the actual number of active readers and not on the total number of readers in the system. With a novel use of secret sharing techniques combined with write back throttling we present the first solution to tolerate Byzantine readers information theoretically, without the use of cryptographic techniques based on unproven number-theoretic assumptions.

UR - http://www.scopus.com/inward/record.url?scp=38049041557&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38049041557&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-75142-7_4

DO - 10.1007/978-3-540-75142-7_4

M3 - Conference contribution

AN - SCOPUS:38049041557

SN - 9783540751410

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 7

EP - 19

BT - Distributed Computing - 21st International Symposium, DISC 2007, Proceedings

PB - Springer Verlag

T2 - 21st International Symposium on Distributed Computing, DISC 2007

Y2 - 24 September 2007 through 26 September 2007

ER -

Bounded wait-free implementation of optimally resilient byzantine storage without (unproven) cryptographic assumptions

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this