Skip to main content

On the Optimality of Optimistic Responsiveness

Publication ,  Conference
Shrestha, N; Abraham, I; Ren, L; Nayak, K
Published in: Proceedings of the ACM Conference on Computer and Communications Security
October 30, 2020

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 latency 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 latency when the designated sender is honest and the optimistic commit can tolerate at least one fault. We experimentally evaluate this protocol and show that it achieves throughput comparable to state-of-the-art synchronous and partially synchronous protocols and under optimistic conditions achieves latency better than the state-of-the-art. Our second upper bound result achieves optimal optimistic and synchronous commit latency 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.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Proceedings of the ACM Conference on Computer and Communications Security

DOI

ISSN

1543-7221

ISBN

9781450370899

Publication Date

October 30, 2020

Start / End Page

839 / 857
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Shrestha, N., Abraham, I., Ren, L., & Nayak, K. (2020). On the Optimality of Optimistic Responsiveness. In Proceedings of the ACM Conference on Computer and Communications Security (pp. 839–857). https://doi.org/10.1145/3372297.3417284
Shrestha, N., I. Abraham, L. Ren, and K. Nayak. “On the Optimality of Optimistic Responsiveness.” In Proceedings of the ACM Conference on Computer and Communications Security, 839–57, 2020. https://doi.org/10.1145/3372297.3417284.
Shrestha N, Abraham I, Ren L, Nayak K. On the Optimality of Optimistic Responsiveness. In: Proceedings of the ACM Conference on Computer and Communications Security. 2020. p. 839–57.
Shrestha, N., et al. “On the Optimality of Optimistic Responsiveness.” Proceedings of the ACM Conference on Computer and Communications Security, 2020, pp. 839–57. Scopus, doi:10.1145/3372297.3417284.
Shrestha N, Abraham I, Ren L, Nayak K. On the Optimality of Optimistic Responsiveness. Proceedings of the ACM Conference on Computer and Communications Security. 2020. p. 839–857.

Published In

Proceedings of the ACM Conference on Computer and Communications Security

DOI

ISSN

1543-7221

ISBN

9781450370899

Publication Date

October 30, 2020

Start / End Page

839 / 857