@prefix dcat: . @prefix dct: . @prefix foaf: . @prefix vcard: . @prefix xsd: . a dcat:Dataset ; dct:description """ A notion of a universal construction suited to distributed computing has been introduced by M. Herlihy in his celebrated paper "Wait-free synchronization" (ACM TOPLAS, 1991). A universal construction is an algorithm that can be used to wait-free implement any object defined by a sequential specification. Herlihy's paper shows that the basic system model, which supports only atomic read/write registers, has to be enriched with consensus objects to allow the design of universal constructions. The generalized notion of a k-universal construction has been recently introduced by Gafni and Guerraoui (CONCUR, 2011). A k-universal construction is an algorithm that can be used to simultaneously implement k objects (instead of just one object), with the guarantee that at least one of the k constructed objects progresses forever. While Herlihy's universal construction relies on atomic registers and consensus objects, a k-universal construction relies on atomic registers and k-simultaneous consensus objects (which are wait-free equivalent to k-set agreement objects in the read/write system model). This paper significantly extends the universality results introduced by Herlihy and Gafni-Guerraoui. In particular, we present a k-universal construction which satisfies the following five desired properties, which are not satisfied by the previous k-universal construction: (1) among the k objects that are constructed, at least l objects (and not just one) are guaranteed to progress forever; (2) the progress condition for processes is wait-freedom, which means that each correct process executes an infinite number of operations on each object that progresses forever; (3) if any of the k constructed objects stops progressing, all its copies (one at each process) stop in the same state; (4) the proposed construction is contention-aware, in the sense that it uses only read/write registers in the absence of contention; and (5) it is generous with respect to the obstruction-freedom progress condition, which means that each process is able to complete any one of its pending operations on the k objects if all the other processes hold still long enough. The proposed construction, which is based on new design principles, is called a (k, l)-universal construction. It uses a natural extension of k-simultaneous consensus objects, called (k, l)-simultaneous consensus objects ((k, l)-SC). Together with atomic registers, (k, l)-SC objects are shown to be necessary and sufficient for building a (k, l)-universal construction, and, in that sense, (k, l)-SC objects are (k, l)-universal. """ ; dct:identifier "Report N°: PI-2014" ; dct:issued "2026-05-05T10:56:14.674753"^^xsd:dateTime ; dct:language "en" ; dct:modified "2026-05-05T10:56:14.674757"^^xsd:dateTime ; dct:publisher ; dct:title "Distributed Universality: Contention-Awareness, Wait-freedom, Object Progress, and Other Properties" ; dcat:contactPoint [ a vcard:Organization ; vcard:fn "CCSD" ] ; dcat:distribution ; dcat:keyword "asynchronous-readwrite-system", "consensus", "contention-awareness", "crash-failures", "infoeu-reposemanticsreport", "infoinfo-dccomputer-science-csdistributed-parallel-and-cluster-computing-csdc", "k-set-agreement", "k-simultaneous-consensus", "non-blocking", "obstruction-freedom", "reports", "state-machine-replication", "universal-construction", "wait-freedom" ; dcat:landingPage . a dcat:Distribution ; dct:format "HTML" ; dct:issued "2026-05-05T10:56:14.684271"^^xsd:dateTime ; dct:modified "2026-05-05T10:56:14.657662"^^xsd:dateTime ; dct:title "Distributed Universality: Contention-Awareness, Wait-freedom, Object Progress, and Other Properties" ; dcat:accessURL . a foaf:Agent ; foaf:name "test_moissonnage_selune" . a foaf:Document .