Mouna Safir (IRIF)
Title: Some new results with k-set agreement
Abstract:
In this talk, I will present our investigation of 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 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≥⌊n/(n−t)⌋+1, and an optimal algorihtm ensuring k-set agreement in t+1 rounds for k≥⌊n/(n−t)⌋. While in the crash asynchronous shared memory systems, we introduce an algorithm that ensure k-set agreement when n>2t for k≥⌊ (n−t)/(n−2t)⌋+1, and an impossibility result for k≤⌊(n−t)/(n−2t)⌋+1.