Resource-cost lower bound for finite-time average-consensus algorithms

Let A\mathcal{A} be a distributed algorithm, let C[0,t1]C_{[0,t_1]} be a communication sequence, and let SVSC\mathrm{S\mathcal{V}SC} denote the relevant sufficient vertex-strongly-connected condition. Let (P) be the knowledge-set property described in the preceding discussion, and let O(nd)O(nd) denote the stated asymptotic resource bound. Resource-cost conjecture. If A\mathcal{A} guarantees average-consensus at time t=t1(+)t=t_1(+) for every communication sequence C[0,t1]C_{[0,t_1]} satisfying the SVSC\mathrm{S\mathcal{V}SC} condition, then A\mathcal{A} must have resource costs at least as great as those of any algorithm satisfying (P). In particular, such an algorithm requires that a set with cardinality upper bounded by at least O(nd)O(nd) can be communicated and stored at each node. This conjecture asserts a lower bound on the communication and storage resources needed for finite-time average consensus under the stated communication condition; the supplied text gives no resolution.

Sources & referencesView supporting material

Primary source

Kevin Topley and Vikram Krishnamurthy, “Average-Consensus Algorithms in a Deterministic Framework”, arXiv:1106.4346 (2011).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.