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 >= left perpendicular n/n-t right perpendicular + 1, and an optimal algorihtm ensuring k-set agreement in t + 1 rounds for k >= left perpendicular n/n-t right perpendicular. While in the crash asynchronous shared memory systems, we introduce an algorithm that ensure k-set agreement when n > 2t for k >= left perpendicular n-t/n-2t right perpendicular + 1, and an impossibility result for k >= left perpendicular n-t/n-2t right perpendicular - 1.