2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

I was wrong the object has an infinite binary consensus number.

if (input = 0) test-and-reset(obj)
prev = fetch-and-add(obj, 2)
if (prev mod 2 = 0)
    decide(0)
else
    decide(1)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.