### On the Optimality of Optimistic Responsiveness

Ittai Abraham, Kartik Nayak, Ling Ren, and Nibesh Shrestha

##### Abstract

Synchronous consensus protocols, by definition, have a worst-case commit latency that depends on the bounded network delay. The notion of optimistic responsiveness was recently introduced to allow synchronous protocols to commit instantaneously when some optimistic conditions are met. In this work, we revisit this notion of optimistic responsiveness and present optimal latency results. We present a lower bound for Byzantine Broadcast that relates the latencies of optimistic and synchronous commits when the designated sender is honest and while the optimistic commit can tolerate some faults. We then present two matching upper bounds for tolerating f faults out of n = 2f +1 parties. Our first upper bound result achieves optimal optimistic and synchronous commit latencies when the designated sender is honest and the optimistic commit can tolerate some faults. Our second upper bound result achieves optimal optimistic and synchronous commit latencies when the designated sender is honest but the optimistic commit does not tolerate any faults. The presence of matching lower and upper bound results make both of the results tight for n = 2f + 1. Our upper bound results are presented in a state machine replication setting with a steady state leader who is replaced with a view-change protocol when they do not make progress. For this setting, we also present an optimistically responsive protocol where the view-change protocol is optimistically responsive too.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. ACM CCS 2020
DOI
10.1145/3372297.3417284
Keywords
Distributed computingblockchainsconsensus protocolsSMRSynchronyoptimistic responsiveness
Contact author(s)
nxs4564 @ rit edu
History
2020-10-02: last of 2 revisions
See all versions
Short URL
https://ia.cr/2020/458

CC BY

BibTeX

@misc{cryptoeprint:2020/458,
author = {Ittai Abraham and Kartik Nayak and Ling Ren and Nibesh Shrestha},
title = {On the Optimality of Optimistic Responsiveness},
howpublished = {Cryptology ePrint Archive, Paper 2020/458},
year = {2020},
doi = {10.1145/3372297.3417284},
note = {\url{https://eprint.iacr.org/2020/458}},
url = {https://eprint.iacr.org/2020/458}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.