2023/10/03 by Carole, Delporte-Gallet, Hugues, Fauconnier, Mouna, Safir
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2310.01976
In this article, we investigate the solvability of k-set agreement among n processes in distributed systems prone to different types of process failures. Specifically, we 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 of processes. Our goal is to address the gaps left by previous works\citeSSS,AsynchKset in these areas. For Byzantine failures case we consider systems with authentication where processes have unforgeable signatures. For synchronous message-passing systems, we present an authenticated algorithm that achieves k-set agreement in only two rounds, with no constraints on the number of faults t, with k determined as k ≥ \lfloor (n)/(n-t) \rfloor + 1. In fact the lower bound for k is k ≥ \lfloor (n)/(n-t) \rfloor that is obtained by an algorithm based on traditional consensus with t+1 rounds. In asynchronous shared memory systems, we introduce an algorithm that accomplishes k-set agreement for values of k greater than \lfloor (n-t)/(n-2t) \rfloor +1. This algorithm uses a snapshot primitive to handle crash failures and enable effective set agreement.