Question

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.

Thanks

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top