I was given an object with exactly 2 operations
test-and-reset that sets the value of the object to 0 only if it was previously set to 1 and does not return a value and
fetch-and-add(v) which adds
v to the value of the object and returns the previous value.
I am almost sure the consensus number of this object is 2 and I think I found an algorithm for it (I should mention the problem is binary consensus):
if input = 0 test-and-reset(obj) prev = fetch-and-add(obj, 3) if (prev != 2) decide(0) else decide(1) else prev = fetch-and-add(obj, 1) if (prev = 0 or prev = 3) decide(0) else decide(1)
The problem was to find a wait-free algorithm an algorithm for
n processes using any number of these objects (
n is known).
The problem is that I an not sure if I am right (I'm pretty sure and this holds me back on this idea)? And if I am right no idea how to use this to solve the problem.