Resource-cost lower bound for finite-time average-consensus algorithms
Resource-cost lower bound for finite-time average-consensus algorithms
Let be a distributed algorithm, let be a communication sequence, and let denote the relevant sufficient vertex-strongly-connected condition. Let (P) be the knowledge-set property described in the preceding discussion, and let denote the stated asymptotic resource bound. Resource-cost conjecture. If guarantees average-consensus at time for every communication sequence satisfying the condition, then 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 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.