M.Sc Thesis

M.Sc StudentAvidor Zvi
Subjectn-Set Consensus when Inputs are Restricted
DepartmentDepartment of Computer Science
Supervisor PROF. Hagit Attiya


A protocol solving the k-set consensus problem has to provide three properties: k-agreement - non-faulty processes have to decide on at most k values, validity - every decision value must be an input value of some process, and termination - each non-faulty process must stop with a decision value after some finite number of steps. It has been proved that this problem can be solved using only read / write operations in the presence of f crash failures if and only if f < k.

One way to subvert this impossibility result is to restrict the possible assignments of input values to processes. This thesis presents a new problem, DS,DL-restricted k-set consensus, which limits the possible input vectors to a set DS, and requires termination of non-faulty processes only when the initial configuration is taken from a smaller set, DL.

A characterization of the finite sets that allow a wait-free solution of DS,DL-restricted n-set consensus in a system with n+1 processes, using only read and write operations is proved. Using this characterization, a polynomial algorithm is provided, which decides if two sets of input vectors, DS and DL, enable solving DS,DL-restricted n-set consensus or not.