11.10

Multi-worker Rabia

Definition

Each worker is a separate process. Each worker is associated with a round number. A worker is started with a round number and a value to propose. The worker is closed after it commits a value.

Number of workers $k$: the maximum number of on-going workers at the same time.

Single-worker mode: if there is any on-going worker, then no new worker can be started.

Multi-worker mode: if the number of on-going workers is less than $k$, then a new worker can be started.

On both modes, a new worker starts with the smallest value in the priority queue.

The fix

If a worker with round number $seq$ commits a $\perp$, then the server is set to single-worker mode, until a non-$\perp$ value is committed at some future round (round number greater than $seq$).

Proof of liveness

We prove that, after all requests are delivered to the servers, if there is still an uncommitted value, then for the following $(k+1)$ consecutive rounds, at least one new value is committed. We prove this by showing that, if the following $k$ consecutive rounds $\{seq,seq+1,\dots ,seq+k-1\}$ are all committed with $\perp$, then a new value must be committed at round $(seq+k)$.

Let $v$ be the smallest value at is not committed at rounds $\{1,2,\dots ,seq-1\}$. (If all the servers operate in single-worker mode, then $v$ should be the value proposed by every server at round $seq$.) We prove that $v$ is committed at round $(seq+k)$.

For any server, when it starts a worker for round $(seq+k)$, it must be in the single-worker mode. Consider the other on-going workers of that server at that time. The number of on-going workers is less than $k$ and each worker is associated with a round number smaller than $(seq+k)$. So there must be a round number $r\in \{seq,seq+1,\dots ,seq+k-1\}$ such that the worker with round number $r$ is already committed. So the server was set to single-worker mode when it knew the result of round $r$. The server also have no chance to exit single-worker mode, since all the rounds after $r$ and before $(seq+k)$ are committed with $\perp$.

Since the server is in single-worker mode, it must propose the smallest value in the priority queue, which is $v$. This is true for all servers, so $v$ is committed at round $(seq+k)$.