Convex decreasing algorithms: Distributed synthesis and finite-time termination in higher dimension

James C Melbourne, Govind Saraswat, Vivek Khatana, Sourav Patel, Murti V. Salapaka

Research output: Contribution to journalArticlepeer-review

Abstract

We introduce a general mathematical framework for distributed algorithms, and a monotonicity property frequently satisfied in application. These properties are leveraged to provide finite-time guarantees for converging algorithms, suited for use in the absence of a central authority. A central application is to consensus algorithms in higher dimension. These pursuits motivate a new peer to peer convex hull algorithm which we demonstrate to be an instantiation of the described theory. To address the diversity of convex sets and the potential computation and communication costs of knowing such sets in high dimension, a lightweight norm based stopping criteria is developed. More explicitly, we give a distributed algorithm that terminates in finite time when applied to consensus problems in higher dimensions and guarantees the convergence of the consensus algorithm in norm, within any given tolerance. Applications to consensus least squared estimation and distributed function determination are developed. The practical utility of the algorithm is illustrated through MATLAB simulations.

Original languageEnglish (US)
JournalUnknown Journal
StatePublished - Jul 26 2020

Fingerprint Dive into the research topics of 'Convex decreasing algorithms: Distributed synthesis and finite-time termination in higher dimension'. Together they form a unique fingerprint.

Cite this