Brooks-Iyengar Algorithm

The Brooks-Iyengar Algorithm or Brooks-Iyengar Hybrid Algorithm is a distributed algorithm, that improves both the precision and accuracy of the measurements taken by a distributed sensor network, even in the presence of faulty sensors.
Background
The Brooks-Iyengar hybrid algorithm 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. This seminal algorithm for the first time unified these disparate fields. Essentially, it combines Dolev’s 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). However the bandwidth requirement will also increase. The algorithm has applications in distributed control, software reliability, High-Performance Computing . , etc.
Algorithm
STEP 1: Each PE receives the values from all other PES and forms a set V.

STEP 2: Perform the optimal region algorithm on V and returns 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 characteristics

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

Main Menu

See Also

Main Menu