Journal article
Trading accuracy for speed in approximate consensus
Knowledge engineering review, Vol.31(4), pp.325-342
09/2016
DOI: 10.1017/S0269888916000175
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(diameter
2) for Laplacian-based), unidirectional PLD-consensus is faster and more resilient than bidirectional PLD-consensus, but exhibits higher variance in the converged value.
Details
- Title: Subtitle
- Trading accuracy for speed in approximate consensus
- Creators
- Jacob Beal - RTX
- Resource Type
- Journal article
- Publication Details
- Knowledge engineering review, Vol.31(4), pp.325-342
- Publisher
- Cambridge University Press
- DOI
- 10.1017/S0269888916000175
- ISSN
- 0269-8889
- eISSN
- 1469-8005
- Number of pages
- 18
- Alternative title
- J. BEAL; Trading accuracy for speed in approximate consensus
- Language
- English
- Date published
- 09/2016
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984627333402771
Metrics
1 Record Views