Sr-9-wyk-1.0-Slajd10
Definicja uszeregowania legalnego
Nie każde uszeregowanie operacji wykonanych w systemie rozproszonym jest możliwe do zrealizowania w praktyce. Będziemy rozważać tylko uszeregowania legalne . Legalność oznacza, że odczyt wartości v ze zmiennej x jest możliwy tylko wtedy, gdy nie było żadnego innego zapisu do zmiennej x wartości różnej od v , który znajdowałby się w uszeregowaniu procesu czytającego po zapisie wartości v a przed odczytem wartości v . Co więcej: nie może być miedzy zapisem wartości v a jej odczytem również operacji odczytu wartości innej niż v . Założenia te są dość intuicyjne jeżeli weźmiemy pod uwagę działanie pamięci lokalnej w węźle. Każda zmienna ma w pamięci swoją pojedynczą lokalizację i odczyt zwraca zawsze ostatnio zapisaną wartość.
Dla uproszczenia rozważań (nie redukując jednak ogólności rozważań) będziemy zakładać, że każdy zapis i odczyt dotyczy unikalnej wartości v . Innymi słowy, wartość zapisywana będzie jednoznacznie identyfikować konkretną operację zapisu.
