Brooks–Iyengar algorithm
The Iyengar-Brooks hybrid algorithm[1] for distributed control in the presence of noisy data combines Byzantine agreement with sensor fusion. It bridges the gap between sensor fusion and Byzantine fault tolerance[2]. This seminal algorithm for the first time unified these disparate fields. Essentially, it combines Dolev’s[3] algorithm for approximate agreement with Mahaney and Schneider’s fast convergence algorithm (FCA). The algorithm assumes N processing elements (PEs) t of which are faulty and can behave maliciously. It takes as input either real values with inherent inaccuracy or noise (which can be unknown), or a real value with apriori defined uncertainty, or an interval. The output of the algorithm is a real value with an explicitly specified accuracy. The algorithm runs in O(NlogN) where N is the number of PEs. It is possible to modify this algorithm to correspond to Crusader’s Convergence Algorithm (CCA)[4]. However the bandwidth requirement will also increase. The algorithm has applications in distributed control, software reliability, High-Performance Computing [5]. , etc.
STEP 1: Each PE receives the values from all other PES and forms a set V.
STEP 2: Perform the optimal region algorithm onV and return a set A consisting of the ranges of values where at least N - T PES intersect.
STEP 3: Output the range defined by the lowest lower bound and the largest upper bound in A. These are the accuracy bounds of the answer.
STEP 4: Sum the midpoints of each range in A multiplied by the number of sensors whose readings intersect in that range, and divide by the number of factors.
This is the answer.
Algorithm
1. Faulty PEs tolerated = <N/3
2. Maximum faculty PEs = <2N/3
3. Complexity = O (N log N)
4. Order of Network Bandwidth = O (N)
5. Convergence = 2t/N
6. Accuracy = Limited by input
7.Iterates for Precision = often
8.Precision over accuracy = no
9.Accuracy over Precision = no
- ^ Richard Brooks, S.S. Iyengar, Robust Distributed Computing, Sensing Algorithm, IEEE 1996.
- ^ D. Dolev, “The Byzantine Generals Strike Again,”J. Algorithms, 1982, pp. 14-30.
- ^ L. Lamport, R. Shostak, and M. Pease, “The Byzantine Generals Problem,” ACM Trans. Program. Lung. Syst., July 1982, pp. 382-401..
- ^ D. Dolev et al., “Reaching Approximate Agreement in the Presence of Faults,”J. ACM, July 1986, pp. 499-516.
- ^ S. Mahaney and F. Schneider. “Inexact Agreement: Accuracy, Precision, and Graceful Degradation,” Proc. Fourth ACM Symp. Principles ofDistributed Computing, ACM Press, New York, 1985, pp. 237-249