M.Sc Thesis | |

M.Sc Student | Avidor Zvi |
---|---|

Subject | n-Set Consensus when Inputs are Restricted |

Department | Department 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, *D _{S},D_{L}-restricted
k-set consensus*, which limits the possible input vectors to a set

A characterization of
the finite sets that allow a wait-free solution of *D _{S},D_{L}*-restricted