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.

Link to the seminal paper on the subject: cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf — Matt Timmermans
– Matt Timmermans, Commented Jul 1 at 13:17

Matt Timmermans · Accepted Answer · 2025-07-01 13:58:39Z

5

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

Every process simply swaps in its own ID. Then:

The first one knows from the counter that it is the winner;
The second one knows from the counter that it lost, and it got the winning process ID from the swap;
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.

edited Jul 1 at 13:58

answered Jul 1 at 13:22

Matt Timmermans

60.9k3 gold badges57 silver badges106 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

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

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related