Brooks–Iyengar algorithm

The Brooks–Iyengar algorithm or FuseCPA Algorithm or Brooks–Iyengar hybrid algorithm^[1] is a distributed algorithm that improves both the precision and accuracy of the interval measurements taken by a distributed sensor network, even in the presence of faulty sensors.^[2] The sensor network does this by exchanging the measured value and accuracy value at every node with every other node, and 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. The algorithm is fault-tolerant and distributed. It could also be used as a sensor fusion method. The precision and accuracy bound of this algorithm have been proved in 2016.^[3]

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.^[4] This seminal algorithm unified these disparate fields for the first time. Essentially, it combines Dolev's^[5] 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),^[6] however, the bandwidth requirement will also increase. The algorithm has applications in distributed control, software reliability, High-performance computing, etc.^[7]

Algorithm

The Brooks–Iyengar algorithm is executed in every processing element (PE) of a distributed sensor network. Each PE exchanges their measured interval with all other PEs in the network. The "fused" measurement is a weighted average of the midpoints of the regions found.^[8] The concrete steps of Brooks–Iyengar algorithm are shown in this section. Each PE performs the algorithm separately:

Input:

The measurement sent by PE k to PE i is a closed interval $[l_{k,i},h_{k,i}]$ , $1\leq k\leq N$

Output:

The output of PE i includes a point estimate and an interval estimate

PE i receives measurements from all the other PEs.
Divide the union of collected measurements into mutually exclusive intervals based on the number of measurements that intersect, which is known as the weight of the interval.
Remove intervals with weight less than $N-\tau$ , where $\tau$ is the number of faulty PEs
If there are L intervals left, let $A_{i}$ denote the set of the remaining intervals. We have $A_{i}=\{(I_{1}^{i},w_{1}^{i}),\dots ,(I_{L}^{i},w_{L}^{i})\}$ , where interval $I_{l}^{i}=[l_{I_{l}^{i}},h_{I_{l}^{i}}]$ and $w_{l}^{i}$ is the weight associated with interval $I_{l}^{i}$ . We also assume $h_{I_{l}^{i}}\leq h_{I_{l+1}^{i}}$ .
Calculate the point estimate $v_{i}'$ of PE i as $v_{i}'={\frac {\sum _{l}{\frac {(l_{I_{l}^{i}}+h_{I_{l}^{i}})\cdot w_{l}^{i}}{2}}}{\sum _{l}w_{l}^{i}}}$ and the interval estimate is $[l_{I_{1}^{i}},h_{I_{L}^{i}}]$

Example:

Consider an example of 5 PEs, in which PE 5 ( $S_{5}$ ) is sending wrong values to other PEs and they all exchange the values.

The values received by $S_{1}$ are in the next Table.

	$S_{1}$	$S_{2}$	$S_{3}$	$S_{4}$	$S_{5}$
$S_{1}$ values	$[2.7,6.7]$	$[0,3.2]$	$[1.5,4.5]$	$[0.8,2.8]$	$[1.4,4.6]$

We draw a Weighted Region Diagram (WRD) of these intervals, then we can determine $A_{1}$ for PE 1 according to the Algorithm:

$A_{1}=\{([1.5,2.7],4),([2.7,2.8],5),([2.8,3.2],4)\}$

which consists of intervals where at least 4(= $N-\tau$ = 5−1) measurements intersect. The output of PE 1 is equal to

${\frac {4*{\frac {1.5+2.7}{2}}+5*{\frac {2.7+2.8}{2}}+4*{\frac {2.8+3.2}{2}}}{13}}=2.625$

and the interval estimate is $[1.5,3.2]$

Similar, we could obtain all the inputs and results of the 5 PEs:

PE	Input Intervals	Output Interval Estimation	Output Point Estimation
$S_{1}$	$[2.7,6.7],[0,3.2],[1.5,4.5],[0.8,2.8],[1.4,4.6]$	$[1.5,3.2]$	2.625
$S_{2}$	$[2.7,6.7],[0,3.2],[1.5,4.5],[0.8,2.8],[-0.6,2.6]$	$[1.5,2.8]$	2.4
$S_{3}$	$[2.7,6.7],[0,3.2],[1.5,4.5],[0.8,2.8],[0.9,4.1]$	$[1.5,3.2]$	2.625
$S_{4}$	$[2.7,6.7],[0,3.2],[1.5,4.5],[0.8,2.8],[-0.7,2.5]$	$[1.5,2.8]$	2.375
$S_{5}$	$[2.7,6.7],[0,3.2],[1.5,4.5],[0.8,2.8],[{\text{--}},{\text{--}}]$	——	——

Related algorithms

1982 Byzantine Problem:^[5] The Byzantine General Problem ^[9] as an extension of Two Generals' Problem could be viewed as a binary problem.

1983 Approximate Consensus:^[10] The method removes some values from the set consists of scalars to tolerant faulty inputs.

1985 In-exact Consensus:^[7] The method also uses scalar as the input.

1996 Brooks-Iyengar Algorithm:^[1] The method is based on intervals.

2013 Byzantine Vector Consensus:^[11] The method uses vectors as the input.

2013 Multidimensional Agreement:^[12] The method also use vectors as the input while the measure of distance is different.

We could use Approximate Consensus (scalar-based), Brooks-Iyengar Algorithm (interval-based) and Byzantine Vector Consensus (vector-based) to deal with interval inputs, and the paper ^[3] proved that Brooks–Iyengar algorithm is the best here.

Application

Brooks–Iyengar algorithm is a seminal work and a major milestone in distributed sensing, and could be used as a fault tolerant solution for many redundancy scenarios.^[13] Also, it is easy to implement and embed in any networking systems.^[14]

In 1996, the algorithm was used in MINIX to provide more accuracy and precision, which leads to the development of the first version of RT-Linux.

In 2000, the algorithm was also central to the DARPA SensIT program's distributed tracking program. Acoustic, seismic and motion detection readings from multiple sensors are combined and fed into a distributed tracking system. Besides, it was used to combine heterogeneous sensor feeds in the application fielded by BBN Technologies, BAE systems, Penn State Applied Research Lab(ARL), and USC/ISI.

The Thales Group, a UK Defense Manufacturer, used this work in its Global Operational Analysis Laboratory. It is applied to Raytheon's programs where many systems need to extract reliable data from unreliable sensor network, this exempts the increasing investment in improving sensor reliability. Also, the research in developing this algorithm results in the tools used by the US Navy in its maritime domain awareness software.

In education, Brooks–Iyengar algorithm has been widely used in teaching classes such as University of Wisconsin, Purdue, Georgia Tech, Clemson University, University of Maryland, etc.

In addition to the area of sensor network, other fields such as time-triggered architecture, safety of cyber-physical systems, data fusion, robot convergence, high-performance computing, software/hardware reliability, ensemble learning in artificial intelligence systems could also benefit from Brooks–Iyengar algorithm.

Algorithm characteristics

Faulty PEs tolerated < N/3
Maximum faulty PEs < 2N/3
Complexity = O(N log N)
Order of network bandwidth = O(N)
Convergence = 2t/N
Accuracy = limited by input
Iterates for precision = often
Precision over accuracy = no
Accuracy over precision = no

Awards and recognition

The Inventors of Brooks Iyengar Algorithm Dr Brooks and Dr SS Iyengar received the prestigious 25 year Test of Time Award for his Pioneering Research and high impact of the Brooks-Iyengar Algorithm. The high impact research and how this work has influenced numerous US government programs and commercial products.

Dr SS Iyengar receiving award from Prof Steve Yau, IEEE

Dr SS Iyengar with his student Dr Brooks

References

^ ^a ^b Richard R. Brooks & S. Sithrama Iyengar (June 1996). "Robust Distributed Computing and Sensing Algorithm". Computer. 29 (6): 53–60. doi:10.1109/2.507632. ISSN 0018-9162. Archived from the original on 2010-04-08. Retrieved 2010-03-22.
^ Mohammad Ilyas; Imad Mahgoub (July 28, 2004). Handbook of sensor networks: compact wireless and wired sensing systems (PDF). CRC Press. pp. 25–4, 33–2 of 864. ISBN 978-0-8493-1968-6. Archived from the original (PDF) on June 27, 2010. Retrieved March 22, 2010.
^ ^a ^b Ao, Buke; Wang, Yongcai; Yu, Lu; Brooks, Richard R.; Iyengar, S. S. (2016-05-01). "On Precision Bound of Distributed Fault-Tolerant Sensor Fusion Algorithms". ACM Comput. Surv. 49 (1): 5:1–5:23. doi:10.1145/2898984. ISSN 0360-0300. S2CID 13760223.
^ D. Dolev (Jan 1982). "The Byzantine Generals Strike Again" (PDF). J. Algorithms. 3 (1): 14–30. doi:10.1016/0196-6774(82)90004-9. Retrieved 2010-03-22.
^ ^a ^b L. Lamport; R. Shostak; M. Pease (July 1982). "The Byzantine Generals Problem". ACM Transactions on Programming Languages and Systems. 4 (3): 382–401. CiteSeerX 10.1.1.64.2312. doi:10.1145/357172.357176. S2CID 55899582.
^ D. Dolev; et al. (July 1986). "Reaching Approximate Agreement in the Presence of Faults" (PDF). Journal of the ACM. 33 (3): 499–516. CiteSeerX 10.1.1.13.3049. doi:10.1145/5925.5931. ISSN 0004-5411. S2CID 496234. Retrieved 2010-03-23.
^ ^a ^b S. Mahaney; F. Schneider (1985). "Inexact agreement: Accuracy, precision, and graceful degradation". Proceedings of the fourth annual ACM symposium on Principles of distributed computing - PODC '85. pp. 237–249. CiteSeerX 10.1.1.20.6337. doi:10.1145/323596.323618. ISBN 978-0897911689. S2CID 10858879.
^ Sartaj Sahni and Xiaochun Xu (September 7, 2004). "Algorithms For Wireless Sensor Networks" (PDF). University of Florida, Gainesville. Retrieved 2010-03-23.
^ Lamport, Leslie; Shostak, Robert; Pease, Marshall (1982-07-01). "The Byzantine Generals Problem". ACM Trans. Program. Lang. Syst. 4 (3): 382–401. CiteSeerX 10.1.1.64.2312. doi:10.1145/357172.357176. ISSN 0164-0925. S2CID 55899582.
^ Dolev, Danny; Lynch, Nancy A.; Pinter, Shlomit S.; Stark, Eugene W.; Weihl, William E. (1986-05-01). "Reaching Approximate Agreement in the Presence of Faults". J. ACM. 33 (3): 499–516. CiteSeerX 10.1.1.13.3049. doi:10.1145/5925.5931. ISSN 0004-5411. S2CID 496234.
^ Vaidya, Nitin H.; Garg, Vijay K. (2013-01-01). "Byzantine vector consensus in complete graphs". Proceedings of the 2013 ACM symposium on Principles of distributed computing. PODC '13. New York, NY, USA: ACM. pp. 65–73. arXiv:1302.2543. doi:10.1145/2484239.2484256. ISBN 9781450320658. S2CID 5914155.
^ Mendes, Hammurabi; Herlihy, Maurice (2013-01-01). "Multidimensional approximate agreement in Byzantine asynchronous systems". Proceedings of the forty-fifth annual ACM symposium on Theory of Computing. STOC '13. New York, NY, USA: ACM. pp. 391–400. doi:10.1145/2488608.2488657. ISBN 9781450320290. S2CID 13865698.
^ Kumar, Vijay (2012). "Computational and Compressed Sensing Optimizations for Information Processing in Sensor Network". International Journal of Next-Generation Computing.
^ Ao, Buke (July 2017). "Robust Fault Tolerant Rail Door State Monitoring Systems: Applying the Brooks-Iyengar Sensing Algorithm to Transportation Applications". International Journal of Next-Generation Computing. 8. S2CID 13592515.

[:0-1] Richard R. Brooks & S. Sithrama Iyengar (June 1996). "Robust Distributed Computing and Sensing Algorithm". Computer. 29 (6): 53–60. doi:10.1109/2.507632. ISSN 0018-9162. Archived from the original on 2010-04-08. Retrieved 2010-03-22.

[2] Mohammad Ilyas; Imad Mahgoub (July 28, 2004). Handbook of sensor networks: compact wireless and wired sensing systems (PDF). CRC Press. pp. 25–4, 33–2 of 864. ISBN 978-0-8493-1968-6. Archived from the original (PDF) on June 27, 2010. Retrieved March 22, 2010.

[:1-3] Ao, Buke; Wang, Yongcai; Yu, Lu; Brooks, Richard R.; Iyengar, S. S. (2016-05-01). "On Precision Bound of Distributed Fault-Tolerant Sensor Fusion Algorithms". ACM Comput. Surv. 49 (1): 5:1–5:23. doi:10.1145/2898984. ISSN 0360-0300. S2CID 13760223.

[4] D. Dolev (Jan 1982). "The Byzantine Generals Strike Again" (PDF). J. Algorithms. 3 (1): 14–30. doi:10.1016/0196-6774(82)90004-9. Retrieved 2010-03-22.

[:2-5] L. Lamport; R. Shostak; M. Pease (July 1982). "The Byzantine Generals Problem". ACM Transactions on Programming Languages and Systems. 4 (3): 382–401. CiteSeerX 10.1.1.64.2312. doi:10.1145/357172.357176. S2CID 55899582.

[6] D. Dolev; et al. (July 1986). "Reaching Approximate Agreement in the Presence of Faults" (PDF). Journal of the ACM. 33 (3): 499–516. CiteSeerX 10.1.1.13.3049. doi:10.1145/5925.5931. ISSN 0004-5411. S2CID 496234. Retrieved 2010-03-23.

[:3-7] S. Mahaney; F. Schneider (1985). "Inexact agreement: Accuracy, precision, and graceful degradation". Proceedings of the fourth annual ACM symposium on Principles of distributed computing - PODC '85. pp. 237–249. CiteSeerX 10.1.1.20.6337. doi:10.1145/323596.323618. ISBN 978-0897911689. S2CID 10858879.

[8] Sartaj Sahni and Xiaochun Xu (September 7, 2004). "Algorithms For Wireless Sensor Networks" (PDF). University of Florida, Gainesville. Retrieved 2010-03-23.

[9] Lamport, Leslie; Shostak, Robert; Pease, Marshall (1982-07-01). "The Byzantine Generals Problem". ACM Trans. Program. Lang. Syst. 4 (3): 382–401. CiteSeerX 10.1.1.64.2312. doi:10.1145/357172.357176. ISSN 0164-0925. S2CID 55899582.

[10] Dolev, Danny; Lynch, Nancy A.; Pinter, Shlomit S.; Stark, Eugene W.; Weihl, William E. (1986-05-01). "Reaching Approximate Agreement in the Presence of Faults". J. ACM. 33 (3): 499–516. CiteSeerX 10.1.1.13.3049. doi:10.1145/5925.5931. ISSN 0004-5411. S2CID 496234.

[11] Vaidya, Nitin H.; Garg, Vijay K. (2013-01-01). "Byzantine vector consensus in complete graphs". Proceedings of the 2013 ACM symposium on Principles of distributed computing. PODC '13. New York, NY, USA: ACM. pp. 65–73. arXiv:1302.2543. doi:10.1145/2484239.2484256. ISBN 9781450320658. S2CID 5914155.

[12] Mendes, Hammurabi; Herlihy, Maurice (2013-01-01). "Multidimensional approximate agreement in Byzantine asynchronous systems". Proceedings of the forty-fifth annual ACM symposium on Theory of Computing. STOC '13. New York, NY, USA: ACM. pp. 391–400. doi:10.1145/2488608.2488657. ISBN 9781450320290. S2CID 13865698.

[13] Kumar, Vijay (2012). "Computational and Compressed Sensing Optimizations for Information Processing in Sensor Network". International Journal of Next-Generation Computing.

[14] Ao, Buke (July 2017). "Robust Fault Tolerant Rail Door State Monitoring Systems: Applying the Brooks-Iyengar Sensing Algorithm to Transportation Applications". International Journal of Next-Generation Computing. 8. S2CID 13592515.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]