2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.