Abstrakt. Vi inleder en studie av begränsad klocksynkronisering under en svårare felmodell än den som Lamport och Melliar-Smith föreslog [1985]. Realistiska aspekter av problemet med synkronisering klockor i närvaro av fel beaktas. En aspekt är att klocksynkronisering är en pågående uppgift, alltså antagandet att vissa av processorer aldrig misslyckas är alltför optimistisk. För att klara av denna verklighet föreslår vi självstabiliserande protokoll som stabiliseras under en (tillräckligt lång) period då mindre än en tredjedel av processorerna är felaktiga. En annan aspekt är att klockvärdet för varje processor begränsas. Ett enda övergående fel kan få klockan att nå den övre gränsen. Därför föreslår vi en avgränsad klocka som sveper runt när det är lämpligt. Vi presenterar två randomiserade självstabiliserande protokoll för synkronisering av avgränsade klockor i närvaro av Bysantinska processorfel. Det första protokollet förutsätter att processorer har en gemensam puls, medan det andra protokollet inte. En ny typ av distribuerad disk baserad på den kinesiska resten theorem används som en del av det första protokollet.
Den första algoritmen någonsin för att ta itu med självstabiliserande bysantinska toleranta klocksynkronisering presenteras i REF.
Self-stabilizing clock synchronization in the presence of Byzantine faults
{'venue': 'JACM', 'journal': None, 'mag_field_of_study': ['Computer Science']}