Vi hanterar problemet med att hålla ett kortaste träd rotat vid någon process r i ett nätverk som kan kopplas bort efter topologiska förändringar. Målet är då att upprätthålla ett kortaste träd rotat vid r i dess anslutna komponent, Vr, och få alla processer av andra komponenter att upptäcka att r inte är en del av deras anslutna komponent. Vi föreslår, i den sammansatta atomicitetsmodellen, en tyst självstabiliserande algoritm för detta problem som arbetar i halvanonyma nätverk, där kanterna har strikt positiva vikter. Denna algoritm kräver ingen förkunskaper om nätverkets globala parametrar. Vi bevisar dess riktighet om vi antar den distribuerade orättvisa demonen, den mest allmänna demonen. Stabiliseringstiden i rundor är högst 3nmaxCC + D, där nmaxCC är det maximala antalet icke-root-processer i en ansluten komponent och D är Vr:s humlediameter. Dessutom, om vi dessutom antar att kantvikter är positiva heltal, då stabiliseras det i ett polynom antal steg: nämligen, vi uppvisar en gräns i O(WmaxnmaxCC 3 n), där Wmax är den maximala vikten av en kant och n är antalet processer.
I REF presenterade vi en självstabiliserande kortaste trädkonstruktion med en enda rot i sammansatt atomäritetsmodell med distribuerad orättvis demon; algoritmen är effektiv både när det gäller rundor och rörelser, och tolererar frånkopplingar.
Self-Stabilizing Disconnected Components Detection and Rooted Shortest-Path Tree Maintenance in Polynomial Steps *
{'venue': 'Discrete Mathematics and Theoretical Computer Science, DMTCS, 2017, ISS, pp.14 - 14', 'journal': None, 'mag_field_of_study': ['Computer Science', 'Mathematics']}