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]