AF: Medium: A Fair Prescription for Partial Synchrony

点击翻译按钮获取中文摘要

Partial synchrony refers to computing environments where timing bounds exist for communication delays and processing speeds, but knowledge of these bounds may be limited or unknown. Although such bounds are only implicit, they can still be used to advantage for building reliable distributed systems in the presence of message loss and crashed processors. The central problem however, is how timing parameters for partial synchrony should be modeled, measured, and denominated.Since its inception some 25 years ago, the prevailing paradigm of chronometry-based models has invoked real-time as a formal basis for modeling temporal bounds on message delays and process speeds. Unfortunately, such models are intrinsically limited (and even flawed) as descriptions of empirical distributed systems, because the characteristic property of partial synchrony is not chronometric timeliness, but rather chronological fairness.This project is developing a fundamental theory of partial synchrony based on the notion of chronological fairness. The key technical innovation is that system failures can be detected in executions that are unfair, rather than untimely. This approach leads to greater generality because many untimely executions are still fair. Theoretical results codify a hierarchy of fairness properties, including technical limitations, expressivity, and reducibility to oracular models. Practical results extract fairness models from empirical systems. An integrated critique of chronometric models helps to initiate a broader shift in research trends to focus on fairness-based paradigms of partial synchrony.