A wait-free consensus algorithm for three processes, with a swap object and the fetch-and-increment object together in one atomic step

Question

We know that a swap object consists of a shared register and supports a swap operation between the shared register and any local register, which atomically exchanges the values of the two registers.

A fetch-and-increment object is a shared register that supports a fetch-and-increment operation, which atomically adds 1 to the value of the register and returns the register’s previous value.

It is known that it is not possible to implement a wait-free consensus algorithm for three processes using swap objects and fetch-and-increment objects and atomic registers, when in a single step only one object can be accessed atomically.

Now my question is, how can we implement a wait-free consensus algorithm for three processes (P1, P2 and P3) using: one swap object and one fetch-andincrement object and atomic registers, but let's assume that it is possible to access the swap object and the fetch-and-increment object together in one atomic step!

That is, in one atomic step a process can update the values of the swap and the fetch-and-increment objects and get back their two previous values, and while this step is taking place no other process can access these two objects. Assume that the initial values of all the objects and registers are 0.

Answer 1

There is a simple 3-process consensus algorithm using the object you propose.

Every process simply swaps in its own ID. Then:

1. The first one knows from the counter that it is the winner;

2. The second one knows from the counter that it lost, and it got the winning process ID from the swap;

3. The third one knows from the counter that it lost, and it got a losing process ID from the swap, so it knows that the winner is the other process, because there are only 3.