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?
