On optimal probabilistic asynchronous byzantine agreement

An important problem in the fault tolerant distributed systems is reaching a consensus among a set of non faulty processes, even in the presence of some corrupted processes. The problem is couched in terms of generals attempting to decide on a common plan of attack. This is in fact the well known Byzantine Generals Problem. We present a consensus protocol of O(ln) communication complexity in asynchronous networks (there is no common global clock and message delivery time is indefinite) with a small error probability where n is the number of players and l is the length of message, given l is sufficiently large, such that l > n3. This improves the previous result with O(ln2) communication complexity[5]. Further more, we have proposed a reliable broadcast protocol in asynchronous networks with the assumption that messages delivery time is finite. Both of our protocols can tolerate up to t < n/3 corrupted players and is computationally secure. © Springer-Verlag Berlin Heidelberg 2008.