Search Results

Documents authored by Lewis-Pye, Andrew


Document
Fever: Optimal Responsive View Synchronisation

Authors: Andrew Lewis-Pye and Ittai Abraham

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)


Abstract
View synchronisation is an important component of many modern Byzantine Fault Tolerant State Machine Replication (SMR) systems in the partial synchrony model. Roughly, the efficiency of view synchronisation is measured as the word complexity and latency required for moving from being synchronised in a view of one correct leader to being synchronised in the view of the next correct leader. The efficiency of view synchronisation has emerged as a major bottleneck in the efficiency of SMR systems as a whole. A key question remained open: Do there exist view synchronisation protocols with asymptotically optimal quadratic worst-case word complexity that also obtain linear complexity and responsiveness when moving between consecutive correct leaders? We answer this question affirmatively with a new view synchronisation protocol for partial synchrony assuming partial initial clock synchronisation, called Fever. If n is the number of processors and t is the largest integer < n/3, then Fever has resilience t, and in all executions with at most 0 ≤ f ≤ t Byzantine parties and network delays of at most δ ≤ Δ after GST (where f and δ are unknown), Fever has worst-case word complexity O(fn+n) and worst-case latency O(Δ f + δ).

Cite as

Andrew Lewis-Pye and Ittai Abraham. Fever: Optimal Responsive View Synchronisation. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{lewispye_et_al:LIPIcs.OPODIS.2023.14,
  author =	{Lewis-Pye, Andrew and Abraham, Ittai},
  title =	{{Fever: Optimal Responsive View Synchronisation}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.14},
  URN =		{urn:nbn:de:0030-drops-195041},
  doi =		{10.4230/LIPIcs.OPODIS.2023.14},
  annote =	{Keywords: Distributed Systems, State Machine Replication}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail