I am studying the $k$-gossip problem on dynamic graphs against an adaptive adversary. Essentially, we are given a set of tokens $\mathcal{T}$ which are distributed amongst the nodes such that each token is distributed to at least one node. Importantly, the nodes do not know the value of $k$. The problem is solved when all nodes know all $k$ tokens.

The paper Information Spreading in Dynamic Networks write in their abstract:

Our main result is an $\Omega(nk/\log{n})$ lower bound on the number of rounds needed for any deterministic token-forwarding algorithm to solve $k$-gossip. This resolves an open problem raised in [33], improving their lower bound of $\Omega(n\log{k})$, and matching their upper bound of $O(nk)$ to within a logarithmic factor.

The paper they mention for the $O(nk)$ upper bound gives a protocol for $n$-gossip but not for $(k<n)$-gossip. Is there an easy way to see the $O(nk)$ upper bound for $k$-gossip for dynamic graphs?

We know that $1$-gossip can be solved in $n-1$ rounds, where $n$ is the size of the network if the nodes know $n$. So could we maybe do $1$-gossip $k$ times. The only issue is that the nodes do not know $n$ or $k$, so we can't use this approach.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.