Detta dokument presenterar en randomiserad (Las Vegas) distribuerad algoritm som konstruerar ett minsta spännträd (MST) i viktade nätverk med optimal (upp till polylogaritmiska faktorer) tid och meddelande komplexitet. Denna algoritm körs i Õ (D + ε n) tid och utbyte Õ (m) meddelanden (båda med hög sannolikhet), där n är antalet noder i nätverket, D är diametern, och m är antalet kanter. Detta är den rst distribuerade MST-algoritm som matchar samtidigt den tid lägre gräns för att (D + ε n) Föregående tid och meddelande lägre gränser härleds med hjälp av två helt olika grafkonstruktioner; den befintliga nedre gränskonstruktionen som visar en lägre gräns fungerar inte för den andra. För att komplettera vår algoritm presenterar vi en ny nedre bundet grafkonstruktion där all distribuerad MST-algoritm kräver både rundor (D + ε n) och meddelanden (m).
Nyligen, Pandurangan et al. REF visade en randomiserad algoritm som kan konstruera en MST i O(D + ε n) rundor samtidigt som man använder ett optimalt antal meddelanden, O( på engelska).
A time- and message-optimal distributed algorithm for minimum spanning trees
{'venue': 'STOC 2017', 'journal': None, 'mag_field_of_study': ['Computer Science']}