Vi presenterar en randomiserad algoritm som beräknar en minsta Spanning Tree (MST) i O(log * n) rundor, med hög sannolikhet, i den överbelastade Clique modellen för distribuerad dator. I den här modellen, indata är en graf på n noder, initialt varje nod vet bara sina incidenter kanter, och per runda kan varje två noder byta O(log n) bitar. Vår viktigaste tekniska nyhet är en O(log * n) Graph Connectivity algoritm, vars hjärta är en (rekursiv) skogstillväxt metod, baserad på en kombination av två idéer: en gleshetskänslig skissning som syftar till glesa grafer och en slumpmässig kantprovtagning som syftar till täta grafer. Vårt resultat förbättras betydligt över O(loggloggloggen n) algoritmen av Hegeman et al. [PODC 2015] och algoritmen O(log log n) för Lotker et al. [SPAA 2003; SICOMP 2005].
I den överbelastade klicken kan MST-problemet lösas mycket snabbare: Ghaffari et al. REF gav en algoritm som löser problemet i O(log * n) rundor med meddelanden av storlek O(log n).
MST in Log-Star Rounds of Congested Clique
{'venue': "PODC '16", 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}