Partial Synchrony Based on Set Timeliness

Overview

This paper introduces a new model of partial synchrony for read-write shared memory systems. This model is based on the notion of set timeliness - a natural and straightforward generalization of the seminal concept of timeliness in the partially synchrony model of Dwork, Lynch and Stockmeyer. Despite its simplicity, the concept of set timeliness is powerful enough to define a family of partially synchronous systems that closely match individual instances of the t-resilient k-set agreement problem among n processes, henceforth denoted (t, k, n)-agreement.