research-article

Byzantine disk paxos: optimal resilience with byzantine shared memory

Authors:

Gregory Chockler,

Dahlia MalkhiAuthors Info & Claims

Distributed Computing, Volume 18, Issue 5

Pages 387 - 408

https://doi.org/10.1007/s00446-005-0151-6

Published: 01 April 2006 Publication History

Abstract

We present Byzantine Disk Paxos, an asynchronous shared-memory consensus algorithm that uses a collection of n < 3t disks, t of which may fail by becoming non-responsive or arbitrarily corrupted. We give two constructions of this algorithm; that is, we construct two different t-tolerant (i.e., tolerating up to t disk failures) building blocks, each of which can be used, along with a leader oracle, to solve consensus. One building block is a t-tolerant wait-free shared safe register. The second building block is a t-tolerant regular register that satisfies a weaker termination (liveness) condition than wait freedom: its write operations are wait-free, whereas its read operations are guaranteed to return only in executions with a finite number of writes. We call this termination condition finite writes (FW), and show that wait-free consensus is solvable with FW-terminating registers and a leader oracle. We construct each of these t-tolerant registers from n < 3t base registers, t of which can be non-responsive or Byzantine. All the previous t-tolerant wait-free constructions in this model used at least 4t + 1 fault-prone registers, and we are not familiar with any prior FW-terminating constructions in this model.

We further show tight lower bounds on the number of invocation rounds required for optimal resilience reliable register constructions, or more generally, constructions that use less than 4t + 1 fault-prone registers. Our lower bounds show that such constructions are inherently more costly than constructions that use 4t + 1 registers, and that our constructions have optimal round complexity. Furthermore, our wait-free construction is early-stopping, and it achieves the optimal round complexity with any number of actual failures.

References

[1]

Attiya, H., Bar-Or, A.: Sharing memory with semibyzantine clients and faulty storage servers. In The 22nd Symposium on Reliable Distributed Systems (SRDS) (2003)

[2]

Afek Y., Greenberg D.S., Merritt M., and Taubenfeld G. Computing with faulty shared objects Journal of the ACM 1995 42 6 1231-1274

[3]

Afek Springer 1993 Verlag LNCS

[4]

Bazzi R. Synchronous byzantine quorum systems Distributed Computing 2000 13 1 45-52

[5]

Boichat R., Dutta P., Frolund S., and Guerraoui R. Deconstructing paxos Distributed computing column of the ACM SIGACT News 2003 34 1 47-67

[6]

Bracha G. and Toueg S. Asynchronous consensus and broadcast protocols Journal of the ACM 1985 32 4 824-840

[7]

Cristian, F., Fetzer, C.: The timed asynchronous distributed system model. IEEE Transactions on Parallel and Distributed Systems, pp. 642–657 (1999)

[8]

Chandra T.D., Hadzilacos V., and Toueg S. The weakest failure detector for solving consensus Journal of the ACM 1996 43 4 685-722

[9]

Chockler, G., Malkhi, D.: Active disk paxos with infinitely many processes. In Proceedings of the 21st ACM Symposium on Principles of Distributed Computing (PODC’02) (2002)

[10]

Chockler, G., Malkhi, D., Reiter, M.K.: Backoff protocols for distributed mutual exclusion and ordering. In Proceedings of the 21st International Conference on Distributed Computing Systems, pp. 11–20 (2001)

[11]

Delporte, C., Fauconnier, H., Guerraoui, R.: Failure detection lower bounds on registers and consensus. In Proceedings of the 16th International Symposium on Distributed Computing (DISC) (2002)

[12]

Dwork C., Lynch N., and Stockmeyer L. Consensus in the presence of partial synchrony Journal of the ACM 1988 35 2 288-323

[13]

Garay J.A., Gennaro R., Jutla C., and Rabin T. Secure distributed storage and retrieval Theoretical Computer Science 2000 243 1–2 363-389

[14]

Gafni E. and Lamport L. Disk paxos Distributed Computing 2003 16 1 1-20

[15]

Goodson, G., Wylie, J., Ganger, G., Reiter, M.: Efficient byzantine-tolerant erasure-coded storage. In Proceedings of the International Conference on Dependable Systems and Networks (DSN-2004) (2004)

[16]

Herlihy, M., Luchangco, V., Moir, M.: Obstruction-free synchronization: Double-ended queues as an example In Proceedings of the 23rd International Conference on Distributed Computing Systems (ICDCS), page 522, IEEE Computer Society (2003)

[17]

Haldar S. and Vitanyi P. Bounded concurrent timestamp systems using vector clocks J. ACM 2002 49 1 101-126

[18]

Jayanti P., Chandra T., and Toueg S. Fault-tolerant wait-free shared objects Journal of the ACM 1998 45 3 451-500

[19]

Keidar, I., Rajsbaum, S.: On the cost of fault-tolerant consensus when there are no faults – a tutorial. Technical Report MIT-LCS-TR-821, MIT Laboratory for Computer Science May 2001. Preliminary version in SIGACT News 32(2), pp. 45–63 (2001) (published May 15th 2001)

[20]

Lamport L. On interprocess communication – part ii: Algorithms Distributed Computing 1986 1 2 86-101

[21]

Lamport L. The part-time parliament ACM Transactions on Computer Systems 1998 16 2 133-169

[22]

Lakshmanan S., Ahamad M., and Venkateswaran H. Responsive security for stored data IEEE Trans. on Parallel and Distributed Systems 2003 14 19 818-828

[23]

Lo, W.K., Hadzilacos, V.: Using failure detectors to solve consensus in asynchronous shared-memory systems. In Proceedings of the 8th International Workshop on Distributed Algorithms (WDAG), pp. 280–295. Springer-Verlag, (1994) In: LNCS 857

[24]

Lin, S., Chen, M., Lian, Q., Zhang, Z.: A practical distributed mutual exclusion protocol in dynamic peer-to-peer systems. In 3rd International Workshop on Peer-to-Peer Systems (IPTPS’04) (2004)

[25]

Lynch N.A. and Tuttle M.R. An introduction to Input/Output Automata CWI Quarterly 1989 2 3 219-246

[26]

Martin, J.-P., Alvisi, L. Dahlin, M.: Minimal byzantine storage. In Proceedings of the 16th International Symposium on Distributed Computing (DISC) (2002)

[27]

Malkhi D. and Reiter M. Byzantine quorum systems Distributed Computing 1998 11 4 203-213

[28]

Malkhi D. and Reiter M. An architecture for survivable coordination in large distributed systems IEEE Transactions on Knowledge and Data Engineering 2002 12 2 187-202

[29]

Rodrigues, R., Liskov, B.: Rosebud: A scalable Byzantine-Fault-Tolerant Storage Architecture. Technical Report MIT-LCS-TR-932, MIT Laboratory for Computer Science (2004)

[30]

Vitanyi, P., Awerbuch, B.: Atomic shared register access by asynchronous hardware. In 27th IEEE Symp. Found. Comput. Sci., pp. 233–243 (1986)

[31]

Zhou L., Schneider F.B., Renesse van, and Coca R. A secure distributed on-line certification authority ACM Transactions on Computer Systems 2002 20 4 329-368

Cited By

Alpos OCachin CTackmann BZanolini L(2024)Asymmetric distributed trustDistributed Computing10.1007/s00446-024-00469-137:3(247-277)Online publication date: 28-May-2024
https://dl.acm.org/doi/10.1007/s00446-024-00469-1
Tseng LZhou NDumas CBantikyan TPalmieri RAgrawal KShun J(2023)Distributed Multi-writer Multi-reader Atomic Register with Optimistically Fast Read and WriteProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591086(479-488)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591086
Sheffi GPetrank EScheideler CSpear M(2020)Functional FaultsProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400261(453-463)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400261
Show More Cited By

Index Terms

Byzantine disk paxos: optimal resilience with byzantine shared memory

Index terms have been assigned to the content through auto-classification.

Recommendations

Byzantine disk paxos: optimal resilience with byzantine shared memory
PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing

We present Byzantine Disk Paxos, an asynchronous shared-memory consensus protocol that uses a collection of n > 3t disks, t of which may fail by becoming non-responsive or arbitrarily corrupted. We give two constructions of this protocol; that is, we ...
Self-Stabilizing Byzantine Broadcast
SRDS '14: Proceedings of the 2014 IEEE 33rd International Symposium on Reliable Distributed Systems

We consider the problem of reliably broadcasting messages in a multi-hop network where nodes can fail in some unforeseen manner. We consider the most general failure model: the Byzantine model, where failing nodes may exhibit arbitrary behavior, and ...
Consensus using omega in asynchronous systems with unknown membership and degenerative Byzantine failures
Abstract
We study consensus in asynchronous systems where membership is unknown, and where up to f degenerative Byzantine failures can happen. In our failure model a faulty process can have a Byzantine behavior (i.e., it deviates from its ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Distributed Computing

Distributed Computing Volume 18, Issue 5

Apr 2006

81 pages

ISSN:0178-2770

Issue’s Table of Contents

© Springer-Verlag 2005.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 01 April 2006

Accepted: 01 September 2005

Received: 06 January 2005

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alpos OCachin CTackmann BZanolini L(2024)Asymmetric distributed trustDistributed Computing10.1007/s00446-024-00469-137:3(247-277)Online publication date: 28-May-2024
https://dl.acm.org/doi/10.1007/s00446-024-00469-1
Tseng LZhou NDumas CBantikyan TPalmieri RAgrawal KShun J(2023)Distributed Multi-writer Multi-reader Atomic Register with Optimistically Fast Read and WriteProceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591086(479-488)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591086
Sheffi GPetrank EScheideler CSpear M(2020)Functional FaultsProceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3350755.3400261(453-463)Online publication date: 6-Jul-2020
https://dl.acm.org/doi/10.1145/3350755.3400261
Aguilera MBen-David NGuerraoui RMarathe VZablotchi IRobinson PEllen F(2019)The Impact of RDMA on AgreementProceedings of the 2019 ACM Symposium on Principles of Distributed Computing10.1145/3293611.3331601(409-418)Online publication date: 16-Jul-2019
https://dl.acm.org/doi/10.1145/3293611.3331601
Alagappan RGanesan ALee EAlbarghouthi AChidambaram VArpaci-Dusseau AArpaci-Dusseau RAgrawal NRangaswami R(2018)Protocol-aware recovery for consensus-based storageProceedings of the 16th USENIX Conference on File and Storage Technologies10.5555/3189759.3189762(15-31)Online publication date: 12-Feb-2018
https://dl.acm.org/doi/10.5555/3189759.3189762
Alagappan RGanesan ALee EAlbarghouthi AChidambaram VArpaci-Dusseau AArpaci-Dusseau R(2018)Protocol-Aware Recovery for Consensus-Based Distributed StorageACM Transactions on Storage10.1145/324106214:3(1-30)Online publication date: 3-Oct-2018
https://dl.acm.org/doi/10.1145/3241062
Viotti PDobre DVukolić M(2017)HybrisACM Transactions on Storage10.1145/311989613:3(1-32)Online publication date: 28-Sep-2017
https://dl.acm.org/doi/10.1145/3119896
Mostéfaoui APetrolia MRaynal MJard C(2017)Atomic Read/Write Memory in Signature-Free Byzantine Asynchronous Message-Passing SystemsTheory of Computing Systems10.1007/s00224-016-9699-860:4(677-694)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1007/s00224-016-9699-8
Esiner EKachkeev ABraunfeld SKüpçü AÖzkasap Ö(2016)FlexDPDPACM Transactions on Storage10.1145/294378312:4(1-44)Online publication date: 16-Aug-2016
https://dl.acm.org/doi/10.1145/2943783
(2016)Read/write shared memory abstraction on top of asynchronous Byzantine message-passing systemsJournal of Parallel and Distributed Computing10.1016/j.jpdc.2016.03.01293:C(1-9)Online publication date: 1-Jul-2016
https://dl.acm.org/doi/10.1016/j.jpdc.2016.03.012
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents