Byzantine agreement and network failures
Franky S Ling · Summit (Simon Fraser University) · 1986
Achieving consistency is one of the important issues in distributed computing.In a distributed environment, consistency comes in different forms, e.g.. processors must take the same action at some specified time, different clocks should give approximately the same value, processors have to agree on a critical value, etc.Under the worst kind of failure behavior, this problem has been abstracted as the Byzantine Agreement problem.A new Byzantine Agreement algorithm is presented which uses fewer messages than other currently known algorithms under a certain range of parameters and terminates in an optimal number of rounds of message exchanges.Previous research dealt mainly with processor failures and treated communication/link failures as a special case of processor failure.A necessary and sufficient condition is presented for reaching agreement under simultaneous failure of k processors and I links in terms of a graph property, namely, the connectivity function of a graph.Byzantine failure is assumed, i.e.. no assumptions are made on the behavior of a faulty component, and in particular, malicious actions taken by faulty components to prevent nonfaulty processors from reaching agreement are taken into account.Connectivity function is valuable in recognizing the degree of tolerance of a distributed system.Unfortunately, however, it is shown that computing the fixedpair connectivity function is, in general.NP-complete.Among several classes of iii graphs investigated, it is shown that the problem remains NP-complete for bipartite.chordal, and split graphs; and is solvable in polynomial time for n-cubes, seriesparallel graphs, and other graphs with bounded vertex connectivity.To my parents a d Aunt Siu Ching.