Impossibility of distributed algorithms for TP under limited communication constraints

Let G(0),G(1),G(0),G(1),\ldots be a sequence of communication graphs satisfying the communication constraints specified in Lemma 2, Theorem 2, or Theorem 3, and let TP denote the task defined in Definition 4. The sequence after G(n1)G(n-1) is otherwise unrestricted.

Impossibility claim. Given these communication constraints, there exists no distributed algorithm that can solve TP without further conditions on the sequence of communication graphs after G(n1)G(n-1).

This claim expresses an impossibility result for information dissemination under the stated time-varying digraph constraints. The supplied text does not provide a resolution status beyond the assertion itself, so its status is left open.

Sources & referencesView supporting material

Primary source

Kevin Topley, “Collection and Dissemination of Data on Time-Varying Digraphs”, arXiv:1604.07478 (2016).

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.