Dlaczego linearyzowalność jest właściwością bezpieczeństwa i dlaczego zestawy właściwości bezpieczeństwa są zamknięte?

W rozdziale 13 „Obiekty atomowe” książki „Algorytmy rozproszone” Nancy Lynch udowodniono, że linearyzowalność (znana również jako atomowość) jest właściwością bezpieczeństwa. To znaczy, że jego odpowiednia właściwość śledzenia jest niepusta, zamknięta z prefiksem i zamknięta z ograniczeniem , jak zdefiniowano w sekcji 8.5.3. Nieformalnie właściwość bezpieczeństwa jest często interpretowana jako powiedzenie, że pewne szczególne „złe” rzeczy nigdy się nie zdarzają.

Na tej podstawie mój pierwszy problem jest następujący:

Jakie są zalety linearyzowalności jako właściwości bezpieczeństwa? Czy są jakieś wyniki oparte na tym fakcie w literaturze?

W badaniu klasyfikacji właściwości bezpieczeństwa i właściwości żywotności wiadomo, że właściwość bezpieczeństwa można scharakteryzować jako zbiór zamknięty w odpowiedniej topologii. W pracy „The Safety-Progress Classification” @ 1993 autorstwa Amira Pnueli i in. , przyjęta jest topologia metryczna. Mówiąc dokładniej, właściwość jest zbiorem (skończonych lub nieskończonych) słów nad alfabetem Σ . Właściwość A ( Φ ) składa się ze wszystkich nieskończonych słów σ, tak że wszystkie prefiksy σ należą do Φ . Na przykład, jeśli Φ = a + b ∗ , to$\Phi$$\Sigma$$A(\Phi)$$\sigma$$\sigma$$\Phi$$\Phi = a^{+}b^{\ast}$ . Właściwość nieskończona Π jest definiowana jakowłaściwość bezpieczeństwa,jeżeli Π = A ( Φ ) dla niektórych właściwości skończonych Φ . Metryka d ( σ , σ ′ ) między nieskończonymi słowami σ i σ ′ jest zdefiniowana jako 0, jeśli są one identyczne, a d ( σ , σ ′ ) = 2 $A(\Phi) = a^{\omega} + a^{+}b^{\omega}$$\Pi$$\Pi = A(\Phi)$$\Phi$$d(\sigma, \sigma')$$\sigma$$\sigma'$ przeciwnym razie, gdziejjest długością najdłuższego wspólnego przedrostka, na który się zgadzają. Dzięki tej metodzie właściwość bezpieczeństwa można topologicznie scharakteryzować jako zestawy zamknięte.$d(\sigma, \sigma') = 2^{-j}$$j$

Oto mój drugi problem:

Jak topologicznie scharakteryzować liniowość jako zestawy zamknięte? W szczególności, jaki jest podstawowy zestaw i jaka jest topologia?

Jakie są zalety linearyzowalności jako właściwości bezpieczeństwa? Czy są jakieś wyniki oparte na tym fakcie w literaturze?

Załóżmy, że zostały wdrożone do wspólnej pamięci urządzenia , że tylko spełnia ewentualne linearyzacja , zdefiniowane następująco: w każdym okresie alfa z M , istnieje pewien punkt w czasie T alfa , taki że linearyzacji posiada od czasu T alfa dalej. Zauważ, że na T nie ma górnej granicy . (*) (Jest to sztuczny odpowiednik standardowej definicji właściwości bezpieczeństwa dotyczącej linearyzowalności).$M$$\alpha$$M$$T_\alpha$$T_\alpha$$T$

Taka implementacja pamięci współużytkowanej nie byłaby bardzo użyteczna dla programisty: Należy pamiętać, że jeśli tylko ewentualna linearyzowalność zostanie utrzymana, nie ma żadnych gwarancji na spójność operacji odczytu / zapisu w żadnym „wczesnym” prefiksie przebiegu (przed nieznanym czasem ). Innymi słowy, cokolwiek się zdarzyło do tej pory, nadal możesz rozszerzyć bieżący prefiks przebiegu do takiego, który spełnia ostateczną linearyzację. $T$

(*) Gdyby istniała taka górna granica, ewentualna linearyzacja stałaby się właściwością bezpieczeństwa.

Jak topologicznie scharakteryzować liniowość jako zestawy zamknięte? W szczególności, jaki jest podstawowy zestaw i jaka jest topologia?

Możemy zdefiniować topologię metryczną na zestawie , który jest zbiorem wszystkich możliwych przebiegów algorytmów rozproszonych. Zauważ, że każdy przebieg α ∈ A S Y N C odpowiada nieskończonej sekwencji przejść stanu. Dla α , β ∈ A S Y N C , α ≠ β definiujemy d ( α , β ) : = 2 - N, gdzie $ASYNC$$\alpha \in ASYNC$$\alpha, \beta \in ASYNC$$\alpha \ne \beta$

Najpierw twierdzą, że jest metryka A S Y N C . Z definicji d jest nieujemne, a ∀ α , β ∈ A S Y N C mamy d ( α , β ) = d ( β , α ) . Dla α , β , γ ∈ A S Y N C , nierówność trójkąta d ( α , $d$$ASYNC$$d$$\forall \alpha,\beta \in ASYNC$$d(\alpha,\beta)=d(\beta,\alpha)$$\alpha,\beta,\gamma \in ASYNC$ utrzymuje się trywialnie, jeśli γ = α lub γ = β . Rozważmy teraz przypadek, że d ( α , γ ) ≥ d ( γ , β ) > 0 , tj. D ( α , γ ) = 2 - n 1 i d ( γ , $d(\alpha,\beta) \le d(\alpha,\gamma) + d(\gamma,\beta)$$\gamma=\alpha$$\gamma=\beta$$d(\alpha,\gamma) \ge d(\gamma,\beta) > 0$$d(\alpha,\gamma)=2^{-n_1}$ , dla niektórych wskaźników n 1 ≤ n 2 . Ponieważ γ ma wspólny przedrostek o długości n 2 - 1 z β, ale tylko przedrostek o długości n 1 - 1 z α , wynika z tego, że α i β różnią się przy indeksie n 1 , a zatem d ( α , β ) = d ( α , γ $d(\gamma,\beta)=2^{-n_2}$$n_1\le n_2$$\gamma$$n_2-1$$\beta$$n_1-1$$\alpha$$\alpha$$\beta$$n_1$$d(\alpha,\beta) = d(\alpha,\gamma)$i następuje nierówność trójkąta. Przypadek, w którym następuje analogicznie.$0<d(\alpha,\gamma) < d(\gamma,\beta)$

$d$$\epsilon$$B_\varepsilon(\alpha) = \{ \beta \in ASYNC \mid d(\alpha,\beta) < \varepsilon \}$$\alpha$$S\subseteq ASYNC$$\alpha \notin S$$N$$\beta$$N$$\alpha$$S$$\alpha \notin S$$N\geq 0$$\beta \in ASYNC$$d(\alpha,\beta) < {2^{-N}}\text{,}$$\alpha$$\beta$$\ge N$$\beta \notin S$$S$

[1] James Munkres. Topologia

Jeśli chodzi o twoje pierwsze pytanie - właściwości bezpieczeństwa są w pewnym sensie „najłatwiejszymi” właściwościami w odniesieniu do problemów takich jak sprawdzanie modelu i synteza.

Podstawowym tego powodem jest to, że w podejściu opartym na teorii automatów do metod formalnych rozumowanie o właściwościach bezpieczeństwa sprowadza się do rozumowania o śladach skończonych, co jest łatwiejsze niż standardowe ustawienie śledzenia nieskończonego.

Zobacz pracę Orny Kupferman tutaj jako punkt wyjścia.