Publications Details

Choice coordination with multiple alternatives

Greenberg, D.S.

The Choice Coordination Problem with {kappa} alternatives ({kappa}-CCP) was introduced by Rabin in 1982. The goal is to design a wait-free protocol for n asynchronous processes which causes all correct processes to agree on one out of {kappa} possible alternatives. Each of the {kappa} alternatives has an associated shared register and a solution to the {kappa}-CCP requires that a special symbol be written in exactly one shared register. All correct processes must eventually halt with a pointer to the register containing the special symbol. The difficulty arises from the fact that each process may have a different naming convention for the registers. Protocols requiring the least number of symbols are considered optimal. We gave a brief overview of our results in this paper.