# Distributed Universality: Contention-Awareness, Wait-freedom, Object Progress, and Other Properties

Distributed Universality: Contention-Awareness, Wait-freedom, Object Progress, and Other Properties - Download this document for free, or read online. Document in PDF available to download.

1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE 2 IUF - Institut Universitaire de France 3 IDC - Interdisciplinay Center Herzliya - Israel

Abstract : 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.

Résumé : Cet article explore la notion de construction universelle dans les systèmes distribués. Il présente une construction k-universelle wait-free qui s-adapte à la concurrence à partir d-objets k-consensus.

Keywords : Asynchronous read-write system universal construction consensus k-set agreement k-simultaneous consensus wait-freedom non-blocking obstruction-freedom contention-awareness crash failures state machine replication

Author: ** Michel Raynal - Julien Stainer - Gadi Taubenfeld - **

Source: https://hal.archives-ouvertes.fr/