Search

This article is on k -set agreement (k SA) in an n -process synchronous message-passing system in which up to t processes can commit Byzantine failures. k SA is a decision problem in which at least each correct (i.e., non-Byzantine) process is assumed to propose and decide a value such that at most k different values are decided by the correct processes, in such a way that, if all the correct processes propose the same value v , they will decide v. This article investigates the possibility/impossibility domain of k SA in the presence of Byzantine processes. To this end it first extends a previous result and shows that k SA cannot be solved when (n < 2 t + t k) ∧ (n − t ≥ k + 1). On the positive side, it presents two synchronous round-based algorithms that solve Byzantine k SA. These algorithms are optimal with respect to the value of k and the number of rounds. The first algorithm is a one-round algorithm that has two instances. The first assumes n > 2 t + 1 and solves k SA for k ≥ ⌊ n − t n − 2 t ⌋ + 1 , while the second assumes n ≤ 2 t + 1 and solves k SA for k ≥ t + 1 (so this second case does not require a majority of correct processes). The second algorithm is based on two new notions denoted Square and Regions that allow each correct process to locally build a global knowledge on which processes proposed which values. This algorithm has also two instances. The first assumes n = 3 t and solves 2SA. The second assumes 2 t + 1 < n ≤ 3 t and solves k SA where k = n − t n − 2 t is an integer. It is worth noticing that the results presented in this article "almost" complete the possibility/impossibility cartography of k SA in synchronous Byzantine systems. The only case that remains open is when n − t n − 2 t is not an integer. • Optimal algorithms for k-set agreement in synchronous systems where some processes are Byzantine • Statement of non-trivial impossibility results • Knowledge-based algorithms • Introduction of new proof-oriented concepts (Squares and Regions) • Round Optimal algorithms (1 & 2 rounds) [ABSTRACT FROM AUTHOR]

While consensus (and more generally agreement problems) is at the heart of many coordination problems in asynchronous distributed systems prone to process crashes, it has been shown to be impossible to solve in such systems where processes communicate by message-passing or by reading and writing a shared memory. Hence, these systems must be enriched with additional computational power for consensus to be solved on top of them. This article presents a new restriction of the classical basic computational model that combines process participation and a constraint on failure occurrences that can happen only while a predefined contention threshold has not yet been bypassed. This type of failure is called λ-constrained crashes , where λ defines the considered contention threshold. It appears that when assuming such contention-related crash failures and enriching the system with objects whose consensus number is x ≥ 1 , consensus for n processes can be solved for any n ≥ x assuming up to x failures. The article proceeds incrementally. It first presents an algorithm that solves consensus on top of read/write registers if at most one crash occurs before the contention threshold λ = n − 1 has been bypassed. Then, the article considers two extensions. The first one assumes that the system is enriched with objects whose consensus number is x ≥ 1 , and shows that when λ = n − x , consensus can be solved despite up to x λ -constrained crashes, for any n ≥ x , and when λ = n − 2 x + 1 , consensus can be solved despite up to 2 x − 1 λ -constrained crashes, assuming x divides n. The second extension prolongs the previous results to the k -set agreement problem (which is a natural generalization of consensus). Impossibility results are also presented for the number of λ -constrained failures that can be tolerated. [ABSTRACT FROM AUTHOR]

The failure detector abstraction has been used to solve agreement problems in asynchronous systems prone to crash failures, but so far it has mostly been used in static and complete networks. This paper aims to adapt existing failure detectors in order to solve agreement problems in unknown, dynamic systems. We are specifically interested in the k-set agreement problem. The problem of k-set agreement is a generalization of consensus where processes can decide up to k different values. Although some solutions to this problem have been proposed in dynamic networks, they rely on communication synchrony or make strong assumptions on the number of process failures. In this paper we consider unknown dynamic systems modeled using the formalism of Time-Varying Graphs, and extend the definition of the existing \Pi \Sigma x,y failure detector to obtain the \Pi \Sigma \bot, x,y failure detector, which is sufficient to solve k-set agreement in our model. We then provide an implementation of this new failure detector using connectivity and message pattern assumptions. Finally, we present an algorithm using \Pi \Sigma \bot, x,y to solve k-set agreement. [ABSTRACT FROM AUTHOR]

A notion of a universal construction suited to distributed computing has been introduced by Herlihy in his celebrated paper ' Wait-free synchronization' (ACM Trans Program Lang Syst 13(1):124-149, 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 (Proceedings of 22nd international conference on concurrency theory (CONCUR'11), Springer LNCS 6901, pp 17-27, 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 $$\ell $$ 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,\ell )$$ -universal construction. It uses a natural extension of k-simultaneous consensus objects, called $$(k,\ell )$$ -simultaneous consensus objects ( $$(k,\ell )$$ -SC). Together with atomic registers, $$(k,\ell )$$ -SC objects are shown to be necessary and sufficient for building a $$(k,\ell )$$ -universal construction, and, in that sense, $$(k,\ell )$$ -SC objects are $$(k,\ell )$$ - $$ {universal}$$ . [ABSTRACT FROM AUTHOR]

This paper introduces a generalization of the immediate snapshot object denoted k-immediate snapshot, requiring that the snapshot returned contains at least (n − k) pairs. The case k = n − 1 corresponds to the original immediate snapshot object, which requires that the snapshot returned contains at least one pair 〈process id, value〉 pair, that corresponds to the process id that invoked the operation). The paper first shows that k -immediate snapshot is impossible to implement in an asynchronous read/write system, even if k = n − 2 and t = 1. Then, the paper considers x -set agreement, another object stronger than the classical read/write t -crash read/write model (when x ≤ t), and studies the relation with the k -immediate snapshot object, establishing strong relations linking these two fundamental distributed computing abstractions. The paper shows conditions under which x -set agreement can be solved in read/write systems enriched with k -immediate snapshot objects. It also shwos when k -immediate snapshot and consensus are equivalent. [ABSTRACT FROM AUTHOR]