Reaching agreement on an unknown network with partial graphic information

Abstract

The Byzantine Agreement (BA) is an important topic in the reliable distributed system because the system can cope with the influences from faulty components when the agreement is achieved. In the literature concerned, the BA problem has been well formulated in a Fully Connected Network (FCN) and a Generalized Connected Network (GCN) under the assumption that each processor in the network has the common knowledge of the graphic information about the entire network structure. However, in the real world, each processor may not have the common knowledge of the graphic information about the entire network structure. That is, the processors may only have the partial knowledge as to their own graphic information. In this paper, the Byzantine Agreement problem will be visited in an Unknown Network (UNet) to increase the capability of fault tolerance by allowing faulty processors with dual failure mode. The proposed protocols, the Unknown Agreement Protocol (UAP) and the Relay Channel (RC), use the minimum number of rounds of message exchange and can tolerate the maximum number of faulty processors allowed.