Extending Paxos with Partially Ordered rnd Values for Transactional Mutual Exclusion

Paxos phase‑1 normally requires a proposer to generate an integer n as the round number rnd ; however, the definition of rnd can be generalized from integers to any value in a partially ordered set, and Paxos’s correctness still holds because the algorithm only relies on the size relationship of rnd .

When rnd follows a partial order, Paxos can be configured to use either forced conflict exclusion (similar to two‑phase commit) or non‑forced exclusion (similar to Paxos livelock) to satisfy safety requirements of the consistency protocol.

For example, using the divisibility partial order, define rnd as a positive integer where a is less than b if a divides b . This yields orderings such as 1 < 2 < 6 and 1 < 3 < 6 , while 2 is not less than 3 . In a scenario, proposer P2 completes phase‑1, but proposer P3 cannot because 3 is not greater than 2 ( 3 ≯ 2 ), so P3 abandons its attempt and later uses 6 to finish phase‑1 and then phase‑2, achieving a commit.

In practice, the partially ordered rnd extends Paxos from a one‑dimensional “happens‑before” relation to a multi‑dimensional ordering, akin to multi‑dimensional timestamps.

Consider a storage system with two groups of proposers: one group selects rnd values of the form 2ⁿ to execute transaction A, while the other selects 3ⁿ for transaction B. The two groups are mutually exclusive, ensuring that at most one transaction succeeds (preventing Paxos livelock), while proposers within each group can provide high‑availability failover without a coordinator failure as in 2PC.

Thus, partially ordered Paxos can deliver the transactional mutual exclusion of 2PC together with Paxos’s fault tolerance, allowing the two‑layer architecture of distributed databases such as Spanner (2PC + Paxos) to be simplified into a single layer.