Berkeleyův algoritmus - Berkeley algorithm

The Berkeleyův algoritmus je metoda synchronizace hodin v distribuované výpočty což předpokládá, že žádný stroj nemá přesný zdroj času. Byl vyvinut Gusellou a Zattim na Kalifornské univerzitě v Berkeley v roce 1989.^[1] Jako Cristianův algoritmus, je určen pro použití v intranety.

Algoritmus

Na rozdíl od Cristianův algoritmus, proces serveru v algoritmu Berkeley, nazvaný vůdce, pravidelně volí ostatní následovník procesy. Obecně řečeno, algoritmus je:

1. A vůdce je vybrán prostřednictvím volební proces jako Algoritmus Chang a Roberts.
2. The vůdce hlasuje následovníci kteří svým časem odpovídají podobným způsobem jako Cristianův algoritmus.
3. The vůdce dodržuje zpáteční čas (RTT) zpráv a odhaduje čas každé z nich následovník a jeho vlastní.
4. The vůdce pak zprůměruje hodiny a ignoruje všechny hodnoty, které přijímá daleko za hodnotami ostatních.
5. Namísto odeslání aktualizovaného aktuálního času zpět do druhého procesu, vůdce poté odešle částku (kladnou nebo zápornou), kterou každý z nich následovník musí upravit své hodiny. Tím se zabrání další nejistotě způsobené RTT na internetu následovník procesy.

S touto metodou průměr ruší tendenci driftu jednotlivých hodin. Gusella a Zatti zveřejnili výsledky zahrnující 15 počítačů, jejichž hodiny byly pomocí jejich protokolu synchronizovány do přibližně 20–25 milisekund.

Počítačové systémy se normálně vyhýbají převíjení svých hodin, když obdrží negativní změnu hodin od vůdce. Pokud tak učiníte, rozbije se to vlastnost monotónního času, což je základní předpoklad v určitých algoritmech v samotném systému nebo v programech, jako je udělat. Jednoduchým řešením tohoto problému je zastavení hodin na dobu určenou vedoucím, ale toto zjednodušené řešení může také způsobit problémy, i když jsou méně závažné. U drobných korekcí většina systémů zpomaluje hodiny (známé jako „hodiny zabité“) a korekci provádí po delší dobu.

Při průměrování výsledků je často ignorován každý klient, jehož hodiny se liší o hodnotu mimo danou toleranci. Tím se zabrání tomu, aby byl celkový systémový čas drasticky zkreslen kvůli chybným hodinám.

Reference