Consider a distributed system composed by n processes each one having a unique identifier. Processes communicate by exchanging messages through perfect point-to-point links and are connected through a grid (i.e., each process pi can exchange messages only with processes located at nord, sud, east and west when they exist). Processes are not going to fail, and they initially know only the number of processes in the system N and the identifiers of their neighbors. Processes in the system must agree on a color assignment satisfying the following specification:

Module Name: k-Color assignment

Events: Request: ca, Propose | c : Proposes a color to be adopted. Indication: ca, Decide | c : Outputs a decided color to be adopted by the process

Properties: Termination: Every process eventually decides a color. Validity: If a process decides a color c, then c was proposed by some process or c = default. Integrity: No process decides twice. Weak Agreement: If two processes decide ci and cj then either ci = cj or one of the two is default Color Selection: Let C be the set of proposed colors, if |C| >0 then there exists at least a color ci C that is decided by k processes.

Assuming that 1< k