Header menu link for other important links
X
On optimal probabilistic asynchronous byzantine agreement
Amjed Shareef, Chandrasekharan Pandu Rangan
Published in
2008
Volume: 4904 LNCS
   
Pages: 86 - 98
Abstract
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.
About the journal
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN03029743
Open AccessNo
Concepts (11)
  •  related image
    FAULT TOLERANCE
  •  related image
    Fault tolerant computer systems
  •  related image
    Network protocols
  •  related image
    Probability
  •  related image
    Problem solving
  •  related image
    ASYNCHRONOUS NETWORKS
  •  related image
    Broadcast protocols
  •  related image
    BYZANTINE AGREEMENT PROBLEM
  •  related image
    Communication complexity
  •  related image
    COMPUTATIONALLY BOUNDED BYZANTINE ADVERSARY
  •  related image
    Distributed computer systems