Byzantine fault tolerance for services with commutative operations

Hua Chai; Wenbing Zhao

doi:10.1109/SCC.2014.37

Byzantine fault tolerance for services with commutative operations

Hua Chai
, Wenbing Zhao

Electrical and Computer Engineering

Cleveland State University

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

17 Scopus citations

Abstract

In this paper, we present a comprehensive study on how to achieve Byzantine fault tolerance for services with commutative operations. Recent research suggests that services may be implemented using Conflict-free Replicated Data Types (CRDTs) for highly efficient optimistic replication with the crash-fault model. We extend such studies by adopting the Byzantine fault model, which encompasses crash faults as well as malicious faults. We carefully analyze the threats towards the operations in a system constructed with CRDTs, and propose a lightweight solution to achieve Byzantine fault tolerance with low runtime overhead. We define a set of correctness properties for such systems and prove that the proposed Byzantine fault tolerance mechanisms guarantee these properties. Furthermore, we show that our mechanisms exhibit excellent performance with a proof-of-concept replicated shopping cart service constructed using CRDTs.

Original language	English
Title of host publication	Proceedings - 2014 IEEE International Conference on Services Computing, SCC 2014
Editors	Elena Ferrari, Ravindran Kaliappa, Patrick C.K. Hung
Place of Publication	usa
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	219-226
Number of pages	8
ISBN (Electronic)	9781479950669
DOIs	https://doi.org/10.1109/SCC.2014.37
State	Published - Oct 17 2014
Event	11th IEEE International Conference on Services Computing, SCC 2014 - Anchorage, United States Duration: Jun 27 2014 → Jul 2 2014

Conference

Conference	11th IEEE International Conference on Services Computing, SCC 2014
Country/Territory	United States
City	Anchorage
Period	06/27/14 → 07/2/14

Keywords

Asynchronous communication
Byzantine fault tolerance
CAP theorem
Network partitioning
Optimistic replication

Access to Document

10.1109/SCC.2014.37

Cite this

@inproceedings{48b4540c19fc4014af668045fe5ba60f,

title = "Byzantine fault tolerance for services with commutative operations",

abstract = "In this paper, we present a comprehensive study on how to achieve Byzantine fault tolerance for services with commutative operations. Recent research suggests that services may be implemented using Conflict-free Replicated Data Types (CRDTs) for highly efficient optimistic replication with the crash-fault model. We extend such studies by adopting the Byzantine fault model, which encompasses crash faults as well as malicious faults. We carefully analyze the threats towards the operations in a system constructed with CRDTs, and propose a lightweight solution to achieve Byzantine fault tolerance with low runtime overhead. We define a set of correctness properties for such systems and prove that the proposed Byzantine fault tolerance mechanisms guarantee these properties. Furthermore, we show that our mechanisms exhibit excellent performance with a proof-of-concept replicated shopping cart service constructed using CRDTs.",

keywords = "Asynchronous communication, Byzantine fault tolerance, CAP theorem, Network partitioning, Optimistic replication",

author = "Hua Chai and Wenbing Zhao",

year = "2014",

month = oct,

day = "17",

doi = "10.1109/SCC.2014.37",

language = "English",

pages = "219--226",

editor = "Elena Ferrari and Ravindran Kaliappa and Hung, \{Patrick C.K.\}",

booktitle = "Proceedings - 2014 IEEE International Conference on Services Computing, SCC 2014",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

note = "11th IEEE International Conference on Services Computing, SCC 2014 ; Conference date: 27-06-2014 Through 02-07-2014",

}

Chai, H & Zhao, W 2014, Byzantine fault tolerance for services with commutative operations. in E Ferrari, R Kaliappa & PCK Hung (eds), Proceedings - 2014 IEEE International Conference on Services Computing, SCC 2014., 6930537, Institute of Electrical and Electronics Engineers Inc., usa, pp. 219-226, 11th IEEE International Conference on Services Computing, SCC 2014, Anchorage, United States, 06/27/14. https://doi.org/10.1109/SCC.2014.37

Byzantine fault tolerance for services with commutative operations. / Chai, Hua; Zhao, Wenbing.
Proceedings - 2014 IEEE International Conference on Services Computing, SCC 2014. ed. / Elena Ferrari; Ravindran Kaliappa; Patrick C.K. Hung. usa: Institute of Electrical and Electronics Engineers Inc., 2014. p. 219-226 6930537.

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

TY - GEN

T1 - Byzantine fault tolerance for services with commutative operations

AU - Chai, Hua

AU - Zhao, Wenbing

PY - 2014/10/17

Y1 - 2014/10/17

N2 - In this paper, we present a comprehensive study on how to achieve Byzantine fault tolerance for services with commutative operations. Recent research suggests that services may be implemented using Conflict-free Replicated Data Types (CRDTs) for highly efficient optimistic replication with the crash-fault model. We extend such studies by adopting the Byzantine fault model, which encompasses crash faults as well as malicious faults. We carefully analyze the threats towards the operations in a system constructed with CRDTs, and propose a lightweight solution to achieve Byzantine fault tolerance with low runtime overhead. We define a set of correctness properties for such systems and prove that the proposed Byzantine fault tolerance mechanisms guarantee these properties. Furthermore, we show that our mechanisms exhibit excellent performance with a proof-of-concept replicated shopping cart service constructed using CRDTs.

AB - In this paper, we present a comprehensive study on how to achieve Byzantine fault tolerance for services with commutative operations. Recent research suggests that services may be implemented using Conflict-free Replicated Data Types (CRDTs) for highly efficient optimistic replication with the crash-fault model. We extend such studies by adopting the Byzantine fault model, which encompasses crash faults as well as malicious faults. We carefully analyze the threats towards the operations in a system constructed with CRDTs, and propose a lightweight solution to achieve Byzantine fault tolerance with low runtime overhead. We define a set of correctness properties for such systems and prove that the proposed Byzantine fault tolerance mechanisms guarantee these properties. Furthermore, we show that our mechanisms exhibit excellent performance with a proof-of-concept replicated shopping cart service constructed using CRDTs.

KW - Asynchronous communication

KW - Byzantine fault tolerance

KW - CAP theorem

KW - Network partitioning

KW - Optimistic replication

UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=84919664397&origin=inward

UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=84919664397&origin=inward

U2 - 10.1109/SCC.2014.37

DO - 10.1109/SCC.2014.37

M3 - Conference contribution

SP - 219

EP - 226

BT - Proceedings - 2014 IEEE International Conference on Services Computing, SCC 2014

A2 - Ferrari, Elena

A2 - Kaliappa, Ravindran

A2 - Hung, Patrick C.K.

PB - Institute of Electrical and Electronics Engineers Inc.

CY - usa

T2 - 11th IEEE International Conference on Services Computing, SCC 2014

Y2 - 27 June 2014 through 2 July 2014

ER -

Byzantine fault tolerance for services with commutative operations

Abstract

Conference

Keywords

Access to Document

Other files and links

Cite this