Abstract: Approximate consensus is an important building block for distributed systems, used overtly or implicitly in applications as diverse as formation control, sensor fusion, and synchronization. Laplacian-based consensus, the current dominant approach, is extremely accurate and resilient, but converges slowly. Comparing Laplacian-based consensus to exact consensus algorithms, relaxing the requirements for accuracy and resilience should enable a spectrum of algorithms that incrementally tradeoff accuracy and/or resilience for speed. This manuscript demonstrates that may be so by beginning to populate this spectrum with a new approach to approximate consensus, Power-Law-Driven Consensus (PLD-consensus), which accelerates consensus by sending values across long distances using a self-organizing overlay network. Both a unidirectional and bidirectional algorithm based on this approach are studied. Although both have the same asymptotic O(diameter) convergence time (vs. O(diameter2) for Laplacian-based), unidirectional PLD-consensus is faster and more resilient than bidirectional PLD-consensus, but exhibits higher variance in the converged value.
Mosk-Aoyama D. & Shah D. 2008. Fast distributed algorithms for computing separable functions. IEEE Transactions on Information Theory 54(7), 2997–3007.
Olfati-Saber R. & Murray R. 2004. Consensus problems in networks of agents with switching topology and time-delays. IEEE Transactions on Automatic Control 49(9), 1520–1533.
Xiao L., Boyd S. & Lall S. 2005. A scheme for asynchronous distributed sensor fusion based on average consensus. In Fourth International Symposium on Information Processing in Sensor Networks.
Yu C.-H. & Nagpal R. 2009. Self-adapting modular robotics: a generalized distributed consensus framework. In International Conference on Robotics and Automation (ICRA).
Abstract: Abstract: Approximate consensus is an important building block for distributed systems, used overtly or implicitly in applications as diverse as formation control, sensor fusion, and synchronization. Laplacian-based consensus, the current dominant approach, is extremely accurate and resilient, but converges slowly. Comparing Laplacian-based consensus to exact consensus algorithms, relaxing the requirements for accuracy and resilience should enable a spectrum of algorithms that incrementally tradeoff accuracy and/or resilience for speed. This manuscript demonstrates that may be so by beginning to populate this spectrum with a new approach to approximate consensus, Power-Law-Driven Consensus (PLD-consensus), which accelerates consensus by sending values across long distances using a self-organizing overlay network. Both a unidirectional and bidirectional algorithm based on this approach are studied. Although both have the same asymptotic O(diameter) convergence time (vs. O(diameter2) for Laplacian-based), unidirectional PLD-consensus is faster and more resilient than bidirectional PLD-consensus, but exhibits higher variance in the converged value.
HTML
Acknowledgments
This work is partially supported by the United States Air Force and DARPA under Contract No. FA8750-10-C-0242. The US Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of DARPA or the US Government.
In particular, t is replaced with τ(t, i), li(t−1) with li(τ(t−1, i)), and lj(t−1) with $l_{j} ({{\rm max}}_{t'} \{ \tau (t',\,j)\!\mid\!\tau (t',\,j)\,\lt\,\tau (t,\,i)\} )$, where τ(t, i) is the time at which the tth round executes at device i.
Note that it is important to use the open interval (0, 1) rather than the closed interval [0, 1], so that 0 can never be selected.
This fraction is selected based on the connectivity parameters used for simulations, such that it excludes all disconnected devices in all static data sets considered. The obvious alternative of measuring only the largest graph component is not used because it does not apply well to the case of mobile devices that transiently connect and disconnect.
