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.
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
log2n 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 ith 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.
Get Answers For Free
Most questions answered within 1 hours.