Question

Show that with sufficiently many n-thread binary consensus objects and atomic registers one can implement

n-thread consensus over n possible values. That is show that you can construct a an n-thread multivalue consensus object where there are only n possible values.

Answer 1

Solution:--------
We agree on the value one bit at a time.The threads share an n-element array of atomic registers, and an array of log₂n consensus objects.
Each thread announces its input in a shared array of atomic registers. At any time each thread has a preference, the value it is trying to convince the others to decide. Initially, each thread’s preferences is its input.
At round i, each thread uses the i^th bit of its preference as input to the i-th binary consensus object. If it wins, it continues to the i+1 consensus with the same preference. If it loses, it scans the announcement array for an input that agrees with all the binary values decided in prior consensus rounds, and uses that value for its preference.