In this post, we will review the definitions of well-known timing models in distributed computing and systems.
Synchronous model
Partially synchronous model
General partially synchronous model
Definition ([1]). After GST, message delays between correct processes are bounded by a constant $\delta$; both GST and $\delta$ are unknown; before GST, messages can get arbitrarily delayed or lost; the processes are equipped with hardware clocks that can drift unboundedly from real time before GST, but do not drift thereafter.
Restricted partially synchronous model
Definition ([2]). After GST, message delays between correct processes are bounded by a constant $\delta$; GST is unknown, but $\delta$ is known; before GST, messages can get arbitrarily delayed; the processes are equipped with hardware clocks that can drift unboundedly from real time before GST, but do not drift thereafter; if $t$ is the time when the first correct process begins the protocol execution, then at least $f$ other correct processes begin the protocol execution at most by time $t+\Gamma$, where $f$ denotes the number of Byzantine processes in the system and $\Gamma$ is a known bound.
Asynchronous model
References
- Making Byzantine Consensus Live, DISC, 2020
- Fever: Optimal Responsive View Synchronization, OPODIS, 2023