I'm facing the following problem: Describe a distributed MST algorithm in time $O(n \log \log n)$
I've managed to think of the following,
- Run GHS(Gallager, Humblet and Spira) algorithm, till there are $(n/(\log n))$ fragments.
This way I believe there's a small thing to do so the finding of roots to connect fragments, will take $\log \log n$.
Basically if there are $\log n$ fragments, searching for the root to connect to, is supposed to take $\log \log n$, because in usual case it takes $\log n$ for $n$ fragments. But I'm really not sure about this one