Unifying Partial Synchrony
<|reference_start|>Unifying Partial Synchrony: The distributed computing literature considers multiple options for modeling communication. Most simply, communication is categorized as either synchronous or asynchronous. Synchronous communication assumes that messages get delivered within a publicly known timeframe and that parties' clocks are synchronized. Asynchronous communication, on the other hand, only assumes that messages get delivered eventually. A more nuanced approach, or a middle ground between the two extremes, is given by the partially synchronous model, which is arguably the most realistic option. This model comes in two commonly considered flavors:   (i) The Global Stabilization Time (GST) model: after an (unknown) amount of time, the network becomes synchronous. This captures scenarios where network issues are transient.   (ii) The Unknown Latency (UL) model: the network is, in fact, synchronous, but the message delay bound is unknown.   This work formally establishes that any time-agnostic property that can be achieved by a protocol in the UL model can also be achieved by a (possibly different) protocol in the GST model. By time-agnostic, we mean properties that can depend on the order in which events happen but not on time as measured by the parties. Most properties considered in distributed computing are time-agnostic. The converse was already known, even without the time-agnostic requirement, so our result shows that the two network conditions are, under one sensible assumption, equally demanding.<|reference_end|>
@article{constantinescu2024unifying,
    title={Unifying Partial Synchrony},
    author={Andrei Constantinescu, Diana Ghinea, Jakub Sliwinski, Roger
  Wattenhofer},
    journal={arXiv preprint arXiv:2405.10249},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.10249},
    primaryClass={cs.DC}
}