Vi presenterar en ny självstabiliserande algoritm för minsta spanning träd (MST) konstruktion. Utrymmet komplexiteten i vår lösning är O(log 2 n) bitar och det konvergerar i O(n 2 ) rundor. Således förbättrar denna algoritm konvergenstiden för tidigare kända självstabiliserande asynkrona MST-algoritmer genom en multiplikativ faktor  till priset av att öka den mest kända rymd komplexiteten med en faktor O(log n). Den viktigaste ingrediensen som används i vår algoritm är designen, för första gången i självstabiliserande inställningar, av ett märkningssystem för att beräkna närmaste gemensamma förfader med endast O(log 2 n) bitar. * En preliminär version av detta dokument har dykt upp
Det snabbaste protokollet som ges i REF konstruerar en MST i O(N 2 ) rundor där N är antalet noder.
Fast Self-Stabilizing Minimum Spanning Tree Construction Using Compact Nearest Common Ancestor Labeling Scheme
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}