Vi studerar problemet med klocksynkronisering i mycket dynamiska nätverk, där kommunikationslänkar kan visas eller försvinna när som helst. Noderna i nätverket är utrustade med hårdvara klockor, men hastigheten på hårdvara klockor kan variera godtyckligt inom specifika gränser, och uppskattningar som noder kan få om klockvärden för andra noder är i sig felaktigt. Vårt mål i denna inställning är att mata ut en logisk klocka vid varje nod, så att de logiska klockor av två noder är inte alltför långt ifrån varandra, och noder som förblir nära varandra i nätverket under en lång tid är bättre synkroniserade än avlägsna noder. Denna egenskap kallas gradient klocka synkronisering. Gradient klocksynkronisering har studerats i stor utsträckning i den statiska inställningen. Vi visar att gränserna för det statiska fallet också gäller för vår mycket dynamiska inställning: om två noder stannar på avstånd d från varandra tillräckligt länge, är det möjligt att synkronisera sina klockor till inom O(d log(D/d)), där D är diametern på nätverket. Detta är känt för att vara optimalt för statiska nätverk, och eftersom ett statiskt nätverk är ett specialfall av ett dynamiskt nätverk, är det också optimalt för dynamiska nätverk. Dessutom visar vi att vår algoritm har optimal stabiliseringstid: när en väg av längd d visas mellan två noder, den tid som krävs tills skev mellan de två noderna reduceras till O(d log(D/d)) är O(D), som vi bevisar är optimal.
Dessutom har problemet med gradient klocksynkronisering studerats för en asynkron variant av modellen REF.
Optimal gradient clock synchronization in dynamic networks
{'venue': "PODC '10", 'journal': None, 'mag_field_of_study': ['Computer Science']}