{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,25]],"date-time":"2026-10-25T15:41:43Z","timestamp":1792942903348,"version":"4.5.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,12,1]],"date-time":"2009-12-01T00:00:00Z","timestamp":1259625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["CNS-0720649CNS-0509338CNS-0411026"],"award-info":[{"award-number":["CNS-0720649CNS-0509338CNS-0411026"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Syst."],"published-print":{"date-parts":[[2009,12]]},"abstract":"<jats:p>A longstanding vision in distributed systems is to build reliable systems from unreliable components. An enticing formulation of this vision is Byzantine Fault-Tolerant (BFT) state machine replication, in which a group of servers collectively act as a correct server even if some of the servers misbehave or malfunction in arbitrary (\u201cByzantine\u201d) ways. Despite this promise, practitioners hesitate to deploy BFT systems, at least partly because of the perception that BFT must impose high overheads.<\/jats:p>\n                  <jats:p>In this article, we present Zyzzyva, a protocol that uses speculation to reduce the cost of BFT replication. In Zyzzyva, replicas reply to a client's request without first running an expensive three-phase commit protocol to agree on the order to process requests. Instead, they optimistically adopt the order proposed by a primary server, process the request, and reply immediately to the client. If the primary is faulty, replicas can become temporarily inconsistent with one another, but clients detect inconsistencies, help correct replicas converge on a single total ordering of requests, and only rely on responses that are consistent with this total order. This approach allows Zyzzyva to reduce replication overheads to near their theoretical minima and to achieve throughputs of tens of thousands of requests per second, making BFT replication practical for a broad range of demanding services.<\/jats:p>","DOI":"10.1145\/1658357.1658358","type":"journal-article","created":{"date-parts":[[2012,10,15]],"date-time":"2012-10-15T15:22:23Z","timestamp":1350314543000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":223,"title":["Zyzzyva"],"prefix":"10.1145","volume":"27","author":[{"given":"Ramakrishna","family":"Kotla","sequence":"first","affiliation":[{"name":"Microsoft Research, Silicon Valley, Mountain View, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lorenzo","family":"Alvisi","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mike","family":"Dahlin","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Allen","family":"Clement","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Edmund","family":"Wong","sequence":"additional","affiliation":[{"name":"The University of Texas at Austin, Austin, TX"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095810.1095817"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095810.1095816"},{"key":"e_1_2_1_3_1","volume-title":"Amazon S3 availability event","author":"Amazon","year":"2008","unstructured":"Amazon . 2008. Amazon S3 availability event : July 20, 2008 . http:\/\/status.aws.amazon.com\/s3-20080720.html. Amazon. 2008. Amazon S3 availability event: July 20, 2008. http:\/\/status.aws.amazon.com\/s3-20080720.html."},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of 14th Annual Eurocrypt Conference (Eurocrypt'97)","author":"Bellare M.","unstructured":"Bellare , M. and Micciancio , D . 1997. A new paradigm for collision-free hashing: Incrementally at reduced cost . In Proceedings of 14th Annual Eurocrypt Conference (Eurocrypt'97) . 163--192. Bellare, M. and Micciancio, D. 1997. A new paradigm for collision-free hashing: Incrementally at reduced cost. In Proceedings of 14th Annual Eurocrypt Conference (Eurocrypt'97). 163--192."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI'99)","author":"Castro M.","unstructured":"Castro , M. and Liskov , B . 1999. Practical Byzantine fault tolerance . In Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI'99) . 173--186. Castro, M. and Liskov, B. 1999. Practical Byzantine fault tolerance. In Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI'99). 173--186."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 4th Symposium on Operating Systems Design and Implementation (OSDI'00)","author":"Castro M.","unstructured":"Castro , M. and Liskov , B . 2000. Proactive recovery in a Byzantine-fault-tolerant system . In Proceedings of the 4th Symposium on Operating Systems Design and Implementation (OSDI'00) . 273--288. Castro, M. and Liskov, B. 2000. Proactive recovery in a Byzantine-fault-tolerant system. In Proceedings of the 4th Symposium on Operating Systems Design and Implementation (OSDI'00). 273--288."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/571637.571640"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1323293.1294280"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1629575.1629602"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI'09)","author":"Clement A.","unstructured":"Clement , A. , Marchetti , M. , Wong , E. , Alvisi , L. , and Dahlin , M . 2009b. Making Byzantine fault tolerant services tolerate Byzantine faults . In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI'09) . 153--168. Clement, A., Marchetti, M., Wong, E., Alvisi, L., and Dahlin, M. 2009b. Making Byzantine fault tolerant services tolerate Byzantine faults. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI'09). 153--168."},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 7th Symposium on Operating Systems Design and Implementation (OSDI'06)","author":"Cowling J.","unstructured":"Cowling , J. , Myers , D. , Liskov , B. , Rodrigues , R. , and Shrira , L . 2006. HQ replication: A hybrid quorum protocol for Byzantine fault tolerance . In Proceedings of the 7th Symposium on Operating Systems Design and Implementation (OSDI'06) . 177--190. Cowling, J., Myers, D., Liskov, B., Rodrigues, R., and Shrira, L. 2006. HQ replication: A hybrid quorum protocol for Byzantine fault tolerance. In Proceedings of the 7th Symposium on Operating Systems Design and Implementation (OSDI'06). 177--190."},{"key":"e_1_2_1_13_1","unstructured":"Dutta P. Guerraoui R. and Vukoli\u0107 M. 2005. Best-Case complexity of asynchronous Byzantine consensus. Tech. rep. EPFL\/IC\/200499 EPFL.  Dutta P. Guerraoui R. and Vukoli\u0107 M. 2005. Best-Case complexity of asynchronous Byzantine consensus. Tech. rep. EPFL\/IC\/200499 EPFL."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/42282.42283"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3149.214121"},{"key":"e_1_2_1_16_1","unstructured":"Gmail. 2006. Lost gmail emails and the future of Web apps. http:\/\/it.slashdot.org (12\/29\/06).  Gmail. 2006. Lost gmail emails and the future of Web apps. http:\/\/it.slashdot.org (12\/29\/06)."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/78969.78972"},{"key":"e_1_2_1_18_1","unstructured":"Hotmail. 2004. Hotmail incinerates customer files. http:\/\/news.com.com (6\/3\/04).  Hotmail. 2004. Hotmail incinerates customer files. http:\/\/news.com.com (6\/3\/04)."},{"key":"e_1_2_1_19_1","unstructured":"Keeney M. Kowalski E. Cappelli D. Moore A. Shimeall T. and Rogers S. 2005. Insider threat study: Computer system sabotage in critical infrastructure sectors. http:\/\/www.cert.org\/archive\/pdf\/insidercross051105.pdf.  Keeney M. Kowalski E. Cappelli D. Moore A. Shimeall T. and Rogers S. 2005. Insider threat study: Computer system sabotage in critical infrastructure sectors. http:\/\/www.cert.org\/archive\/pdf\/insidercross051105.pdf."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1294261.1294267"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the International Conference on Dependable Systems and Networks (DSN'04)","author":"Kotla R.","unstructured":"Kotla , R. and Dahlin , M . 2004. High throughput Byzantine fault tolerance . In Proceedings of the International Conference on Dependable Systems and Networks (DSN'04) . 575--584. Kotla, R. and Dahlin, M. 2004. High throughput Byzantine fault tolerance. In Proceedings of the International Conference on Dependable Systems and Networks (DSN'04). 575--584."},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the USENIX Annual Technical Conference. 129--142","author":"Kotla R.","unstructured":"Kotla , R. , Dahlin , M. , and Alvisi , L . 2007b. SafeStore: A durable and practical storage system . In Proceedings of the USENIX Annual Technical Conference. 129--142 . Kotla, R., Dahlin, M., and Alvisi, L. 2007b. SafeStore: A durable and practical storage system. In Proceedings of the USENIX Annual Technical Conference. 129--142."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/357172.357176"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/359545.359563"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2993.2994"},{"key":"e_1_2_1_27_1","series-title":"Lecture Notes in Computer Science","volume-title":"Lower bounds for asynchronous consensus","author":"Lamport L.","unstructured":"Lamport , L. 2003. Lower bounds for asynchronous consensus . Lecture Notes in Computer Science , vol. 2584 . Springer , 22--23. Lamport, L. 2003. Lower bounds for asynchronous consensus. Lecture Notes in Computer Science, vol. 2584. Springer, 22--23."},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 4th USENIX Symposium on Networked Systems Design and Implementation (NSDI'07)","author":"Li J.","unstructured":"Li , J. and Mazi\u00e8res , D . 2007. Beyond one-third faulty replicas in Byzantine fault tolerant services . In Proceedings of the 4th USENIX Symposium on Networked Systems Design and Implementation (NSDI'07) . 131--144. Li, J. and Mazi\u00e8res, D. 2007. Beyond one-third faulty replicas in Byzantine fault tolerant services. In Proceedings of the 4th USENIX Symposium on Networked Systems Design and Implementation (NSDI'07). 131--144."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/121132.121169"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2006.35"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI'06)","author":"Nightingale E.","unstructured":"Nightingale , E. , Veeraraghavan , K. , Chen , P. , and Flinn , J . 2006. Rethink the sync . In Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI'06) . 1--14. Nightingale, E., Veeraraghavan, K., Chen, P., and Flinn, J. 2006. Rethink the sync. In Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI'06). 1--14."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095810.1095829"},{"key":"e_1_2_1_33_1","unstructured":"OpenSSL. 2007. OpenSSL. http:\/\/www.openssl.org\/.  OpenSSL. 2007. OpenSSL. http:\/\/www.openssl.org\/."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/322186.322188"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1095810.1095830"},{"key":"e_1_2_1_36_1","series-title":"Lecture Notes in Computer Science","volume-title":"The Rampart toolkit for building high-integrity services","author":"Reiter M.","unstructured":"Reiter , M. 1995. The Rampart toolkit for building high-integrity services . Lecture Notes in Computer Science , vol. 938 . Springer , 99--110. Reiter, M. 1995. The Rampart toolkit for building high-integrity services. Lecture Notes in Computer Science, vol. 938. Springer, 99--110."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/502034.502037"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/319151.319159"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/98163.98167"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation (NSDI'08)","author":"Singh A.","unstructured":"Singh , A. , Das , T. , Maniatis , P. , Druschel , P. , and Roscoe , T . 2008. BFT protocols under fire . In Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation (NSDI'08) . 189--204. Singh, A., Das, T., Maniatis, P., Druschel, P., and Roscoe, T. 2008. BFT protocols under fire. In Proceedings of the 5th USENIX Symposium on Networked Systems Design and Implementation (NSDI'08). 189--204."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI'09)","author":"Singh A.","unstructured":"Singh , A. , Fonseca , P. , Kuznetsov , P. , Rodrigues , R. , and Maniatis , P . 2009. Zeno: Eventually consistent Byzantine fault tolerance . In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI'09) . 169--184. Singh, A., Fonseca, P., Kuznetsov, P., Rodrigues, R., and Maniatis, P. 2009. Zeno: Eventually consistent Byzantine fault tolerance. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI'09). 169--184."},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI'09)","author":"Wester B.","unstructured":"Wester , B. , Cowling , J. , Nightingale , E. B. , Chen , P. M. , Flinn , J. , and Liskov , B . 2009. Tolerating latency in replicated state machines through client speculation . In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI'09) . 245--260. Wester, B., Cowling, J., Nightingale, E. B., Chen, P. M., Flinn, J., and Liskov, B. 2009. Tolerating latency in replicated state machines through client speculation. In Proceedings of the 6th USENIX Symposium on Networked Systems Design and Implementation (NSDI'09). 245--260."},{"key":"e_1_2_1_43_1","volume-title":"ZZ: Cheap practical BFT using virtualization. Tech. rep. TR14-08","author":"Wood T.","year":"2008","unstructured":"Wood , T. , Singh , R. , Venkataramani , A. , and Shenoy , P . 2008 . ZZ: Cheap practical BFT using virtualization. Tech. rep. TR14-08 , University of Massachusetts , Amherst, MA . Wood, T., Singh, R., Venkataramani, A., and Shenoy, P. 2008. ZZ: Cheap practical BFT using virtualization. Tech. rep. TR14-08, University of Massachusetts, Amherst, MA."},{"key":"e_1_2_1_44_1","volume-title":"Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI'06)","author":"Yang J.","unstructured":"Yang , J. , Sar , C. , and Engler , D . 2006. Explode: A lightweight, general system for finding serious storage system errors . In Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI'06) . 131--146. Yang, J., Sar, C., and Engler, D. 2006. Explode: A lightweight, general system for finding serious storage system errors. In Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI'06). 131--146."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/945445.945470"}],"container-title":["ACM Transactions on Computer Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1658357.1658358","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1658357.1658358","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T16:25:56Z","timestamp":1750263956000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1658357.1658358"}},"subtitle":["Speculative Byzantine fault tolerance"],"short-title":[],"issued":{"date-parts":[[2009,12]]},"references-count":43,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,12]]}},"alternative-id":["10.1145\/1658357.1658358"],"URL":"https:\/\/doi.org\/10.1145\/1658357.1658358","relation":{},"ISSN":["0734-2071","1557-7333"],"issn-type":[{"value":"0734-2071","type":"print"},{"value":"1557-7333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,12]]},"assertion":[{"value":"2009-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}