The k-set agreement problem is a generalization of the consensus problem： considering a system made up of n processes where each process proposes a value, each non-faulty process has to decide a value such that a dec...The k-set agreement problem is a generalization of the consensus problem： considering a system made up of n processes where each process proposes a value, each non-faulty process has to decide a value such that a decided value is a proposed value, and no more than k different values are decided. While this problem cannot be solved in an asynchronous system prone to t process crashes when t≥ k, it can always be solved in a synchronous system; [t/k]＋1 is then a lower bound on the number of rounds （consecutive communication steps） for the non-faulty processes to decide. The condition-based approach has been introduced in the consensus context. Its aim was to both circumvent the consensus impossibility in asynchronous systems, and allow for more efficient consensus algorithms in synchronous systems. This paper addresses the condition-based approach in the context of the k-set agreement problem. It has two main contributions. The first is the definition of a framework that allows defining conditions suited to the l-set agreement problem and the second is a generic synchronous k-set agreement algorithm based on conditions.展开更多
基金supported by the European Network of Excellence ReSIST.
文摘The k-set agreement problem is a generalization of the consensus problem： considering a system made up of n processes where each process proposes a value, each non-faulty process has to decide a value such that a decided value is a proposed value, and no more than k different values are decided. While this problem cannot be solved in an asynchronous system prone to t process crashes when t≥ k, it can always be solved in a synchronous system; [t/k]＋1 is then a lower bound on the number of rounds （consecutive communication steps） for the non-faulty processes to decide. The condition-based approach has been introduced in the consensus context. Its aim was to both circumvent the consensus impossibility in asynchronous systems, and allow for more efficient consensus algorithms in synchronous systems. This paper addresses the condition-based approach in the context of the k-set agreement problem. It has two main contributions. The first is the definition of a framework that allows defining conditions suited to the l-set agreement problem and the second is a generic synchronous k-set agreement algorithm based on conditions.
