Asynchronous Agreement. So far we have presented an asynchronous broadcast protocol where a designated sender initiates the protocol with a direction. One major weakness of the protocol is that, if the sender is faulty then the protocol might never terminate, because in this case the correct nodes cannot decide whether the sender is faulty and not sending the [init] message, or correct but very slow. On the other hand, in an asynchronous reference frame agreement pro- tocol the main goal is to allow the correct nodes to agree on some direction despite the presence of—up to a cer- tain number of—unidentified faulty nodes in the network. This requires extra caution to make sure that the proto- col eventually terminates. We show that our protocol 3 A-Agree successfully solves this problem by proving theo- rem 1. We repeat the theorem here.
Theorem 1. In a complete network of n nodes that are pairwise connected by public authenticated classical and quantum channels, if a bipartite δ-estimate direction pro- tocol that uses m qubits to achieve success probability
Asynchronous Agreement. Now we give our main protocol A-Agree which uses AR- Cast as a subroutine and allows the correct nodes in an asynchronous network to agree on a reference frame. In Epoch 0 of protocol 3 A-Agree all the nodes proposes a direction which represents their local frame. They broadcast this direction using AR-Cast. All the correct nodes waits for at least (3t + 1) such broadcasts to be complete. Then they enter Epoch 1. Since, there are (3t + 1) correct nodes they will eventually arrive at Epoch
1. In this step all the correct nodes creates a bit string of length n where j’th bit represents if the j’th AR-Cast have been completed successfully in Epoch 0. Then all the nodes sends this bit string to all by playing Asynchronous- IC. After this they enters Epoch 2. In this Epoch every node has the same set of bit strings. They now look for the lowest inter k such that at least (t + 1) bit strings has a 1 in that position. If they have completed that k’th AR-Cast they output their direction received from that broad cast. If they k’th AR-Cast is not complete for him they wait until it completes and then output. The election of k ensures that at least one correct node have completed the k’th AR-Cast so by Consistency of asynchronous reference frame broadcast all the honest nodes will eventually complete the k’th AR-Cast. This ensure that the A-Agree eventually completes. As, there is no loop in this protocol and all the subroutines run in constant expected time. The A-Agree is also a constant expected time protocol.
