Master Thesis
Latency Zoo
State Machine Replication is a fundamental technique for building fault-tolerant distributed systems, allowing multiple replicas to maintain a consistent state despite failures. Many protocols have been proposed for this problem, targeting different models and use cases. Having measurements to characterize the performance of such protocols is useful to be able to compare and choose protocols that best fit the application needs. One key measure is latency, which measures the number of round trips to commit a transaction [1]. There are, however, many different latency notions which measure latency under varying assumptions. These include best-case latency, expected latency, good-case latency, worst-case latency, transaction-expected latency etc. In addition, the definitions of such terms are not standardized and can change between papers. For example, best-case latency characterizes performance under a favorable set of execution conditions, but the assumptions defining these conditions can vary between works. Such differences may concern previous failures, the protocol phase, and the timing assumptions under which the protocol operates, among other factors. Consequently, latency claims that appear similar may not be directly comparable. The main objective of this thesis is to systematically study and classify the latency definitions used in the SMR literature, identify the assumptions underlying them, and develop a unified framework for describing SMR latency. The framework will aim to clarify the relationships between different latency notions and facilitate meaningful comparisons of latency claims across protocols.
References
[1] What is the difference between PBFT, Tendermint, SBFT and HotStuff ?
[2] TOB-SVD: Total-Order Broadcast with Single-Vote Decisions in the Sleepy Model
[3] Simplex Consensus: A Simple and Fast Consensus Protocol