Brooks–Iyengar algorithm
Encyclopedia
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. The sensor network does this by exchanging the measured value and accuracy value at every node with every other node. And it computes the accuracy range and a measured value for the whole network from all of the values collected. Even if some of the data from some of the sensors is faulty, the sensor network will not malfunction.
. It bridges the gap between sensor fusion and Byzantine fault tolerance. This seminal algorithm unified these disparate fields for the first time. 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: see Big O notation
. 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.
STEP 1: Each processing element receives the values from all other processing elements 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 processing elements 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.
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
Background
The Brooks–Iyengar hybrid algorithm for distributed control in the presence of noisy data combines Byzantine agreement with sensor fusionSensor fusion
Sensor fusion is the combining of sensory data or data derived from sensory data from disparate sources such that the resulting information is in some sense better than would be possible when these sources were used individually...
. It bridges the gap between sensor fusion and Byzantine fault tolerance. This seminal algorithm unified these disparate fields for the first time. 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: see Big O notation
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
. 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
Distributed control system
A distributed control system refers to a control system usually of a manufacturing system, process or any kind of dynamic system, in which the controller elements are not central in location but are distributed throughout the system with each component sub-system controlled by one or more...
, software reliability, High-performance computing
High-performance computing
High-performance computing uses supercomputers and computer clusters to solve advanced computation problems. Today, computer systems approaching the teraflops-region are counted as HPC-computers.-Overview:...
, etc.
Algorithm
The Brooks–Iyengar algorithm is executed in every sensor node of a distributed sensor network. Each sensor exchanges their measured value and accuracy value with all other sensors in the network. The accuracy range the algorithm finds is the lowest lower bound and the highest upper bound returned from all the sensors. The "fused" measurement is a weighted average of the midpoints of the regions found.STEP 1: Each processing element receives the values from all other processing elements 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 processing elements 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/32. 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