I try to provide a strict and mathematical rigorous proof to the following problem in Distributed Algorithms.

Prove or make a contradiction: if to vertices $a$ and $b$ on the network $G$ are located on the distance $k$ from each other, and there are $k^2$ different paths on different edges, so it is possible to transfer $k^2$ messages from $a$ to $b$ in time $\text{O}(k)$.

In my opinion. it's not true, I will try to show why. Let's say we have a network as on the picture with vertices $a$ and $b$, all vertices are different and there are 3 paths. The distance from $a$ to $b$ is $k$, in the case of synchronous communication, on every $k/2$ vertices the is collision of $k^2$ messages (the number of paths). In general, it's possible to build a network (not like on the picture), where the worst case occurs (first outgoing messages goes on the longest path and last outgoing message on the shortest path, finally they will make collision again).

Finally, we will get, $\sum_{0}^{\frac{k}{2}} k^2$ - collisions, which is greater than $\text{O}(k)$.

enter image description here

Does it make sense? Is it enough rigorous?

  • 1
    $\begingroup$ I'm not sure what "on different edges" means. Can no two paths share an edge? Otherwise a bottleneck seems easy to construct. $\endgroup$ – Karolis Juodelė Dec 26 '12 at 0:09
  • $\begingroup$ you are right, it's tricky definition, I think it means as you mentioned "no two path share an edges" $\endgroup$ – com Dec 26 '12 at 5:56
  • $\begingroup$ Well, in that case your example doesn't satisfy the condition, right? It would need $k^3$ edges, by pigeonhole principle, but only has $k^2$. With such strict requirement the problem statement seems true. $\endgroup$ – Karolis Juodelė Dec 26 '12 at 10:40
  • $\begingroup$ @KarolisJuodelė, thank you very much for your comments, please correct me if I get it wrong, yes it might be at least $k^3$ edges and $k^2$ paths and messages, but we still can build the paths like on the picture and cause collision on every $k/2$ vertex. $\endgroup$ – com Dec 26 '12 at 15:08
  • $\begingroup$ Honestly, I don't have an understanding of the matter. I deduced that per one unit of time vertices can send or receive any number of messages (otherwise vertices $a$ and $b$ would be unavoidable bottlenecks) and only one message can move forward on one edge (otherwise we get infinite bandwidth). If I'm correct then only edges, not vertices, can form bottlenecks. $\endgroup$ – Karolis Juodelė Dec 26 '12 at 15:22

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.