I'm trying to solve a problem that may arise in a system I am concerned with. It will be uncommon in practice, so I am more concerned about simplicity and correctness than performance. I have N nodes that I want to reach agreement on a boolean value v. F of the nodes might exhibit arbitrary faults. I would like to avoid timing assumptions if possible. The nodes have public keys known to everyone.

Now, suppose N = 5F + 1 and there are 1 or more honest "coordinators" who will assist. A coordinator queries the nodes for their current state, and waits for 4F + 1 signed responses. If all agree on v, then the protocol is done. Otherwise, the coordinator collects the 4F + 1 responses into a vector V and forwards it to each of the N nodes.

If node j has not received a V, it saves it in $\hat V$, sets its current value, $v_j$, to the majority value in V, and initializes a state sequence number, $k_j$, to 1. It then returns $ \{v_j,k_j\} $ as its signed response.

If node j has already received a V then it checks whether V is a valid update by confirming that $k_j$ in V matches its current state sequence number and $k_i >= \hat k_i $ for all i in both V and $\hat V$. If V is valid, it replaces $\hat V$, increments $k_j$ and updates $v_j$ according to the majority in V. In either case it returns it current $ \{v_j,k_j\} $

The coordinator waits for 4F + 1 responses, and terminates protocol if all agree or resubmits new V if not.

As long as there is only 1 active coordinator, a single step should result in at least 4F + 1 nodes returning the same value v. If 4F + 1 nodes return the same value, then at least 3F + 1 non-faulty nodes hold that value, so no subsequent query can receive more than 2F contrary values. Since non-faulty nodes will not accept V containing older values and will not change their current value unless V contains at least 2F + 1 contrary values, it seems like this state is final.

If there is more than 1 active coordinator, then each may find some of their V's rejected by nodes that have incremented their $k_j$ since the coordinator query. If all of the active coordinators submit V that hold the same majority v, then this should have no effect. However, since each coordinator acts on only 4F + 1 responses and F of them might be from faulty nodes who could flip their answer, it is easy to see how 2 coordinators might have valid V yielding different majority v. In that case, each can gather their 4F + 1 responses and resubmit.

To encourage progress when there is contention, the nodes could have a built-in favoritism for one of the two alternatives, say "1". Whenever a node sets it state to 1, it could reject any V with majority 0 for a short period of time. And/or coordinators could implement a random exponential backoff.

Is this correct, as long as the coordinators behave correctly? Given that I am content to have N = 5F + 1, what would be the simplest established algorithm for this problem?

  • $\begingroup$ If you agree the above works when there is only a single coordinator, why not considering only the coordinator with minimal ID, and ignoring the rest? $\endgroup$
    – Ran G.
    Dec 1, 2021 at 12:47
  • $\begingroup$ I guess that would work. So, upon accepting new V, ignore any proposal from higher ID for a period of time. $\endgroup$ Dec 1, 2021 at 16:07
  • $\begingroup$ It depends what you mean by correct. In particular, do you want to ensure termination? If so, first you must make some timing assumptions and then ask the question again. Without timing assumption, the FLP impossibility theorem shows that your algorithm cannot ensure termination. $\endgroup$
    – nano
    Dec 1, 2021 at 18:45
  • $\begingroup$ @nano I do not require all non-faulty nodes to agree on same v, only at least 3F + 1. But wouldn't a random backoff make the algorithm non-deterministic so not subject to FLP? $\endgroup$ Dec 1, 2021 at 19:45
  • $\begingroup$ @nano thinking further, I guess random backoff does not evade FLP because it would be indistinguishable in asynchronous network model? $\endgroup$ Dec 1, 2021 at 20:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.