2023/01/24 by Andrew Lewis-Pye, Ittai Abraham, Lewis-Pye, Andrew +1 · 1 citation
Computer Science · Engineering · #Advanced Vision and Imaging #Distributed #FOS: Computer and information sciences #Image Processing Techniques and Applications #Parallel #Video Analysis and Summarization #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2301.09881
openalex publication_date 2023/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 message complexity and responsiveness when moving between consecutive correct leaders? We answer this question affirmatively with a new view synchronisation protocol for partial synchrony assuming minimal clock synchronisation, called Fever. If n is the number of processors and t is the largest integer