Some New Results With k-Set Agreement

In this article, we investigate the solvability of k-set agreement among n processes in distributed systems prone to different types of process failures. k-set agreement allows each process to propose a value 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. We specially explore two scenarios: synchronous message-passing systems prone to up to t Byzantine failures of processes, and asynchronous shared memory systems prone to up to t crash failures. Our goal is to address the gaps left by previous works [4, 8, 15] in these areas. In the message passing system with Byzantine failures we enrished the system with authentication, we present an algorithm that ensures k-set agreement in only two rounds, with no constraints on the number of faults t, with k determined as \(k \ge \lfloor \frac{n}{n-t} \rfloor + 1\) , and an optimal algorihtm ensuring k-set agreement in \(t+1\) rounds for \(k \ge \lfloor \frac{n}{n-t} \rfloor \) . While in the crash asynchronous shared memory systems, we introduce an algorithm that ensure k-set agreement when \(n > 2t\) for \(k \ge \lfloor \frac{n-t}{n-2t} \rfloor +1\) , and an impossibility result for \(k \le \lfloor \frac{n-t}{n-2t} \rfloor - 1\) .