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

10

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ΦΣA(Φ)σσΦΦ=a+b . 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(Φ)=aω+a+bωΠΠ=A(Φ)Φd(σ,σ)σσ 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(σ,σ)=2jj

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?

hengxin
źródło

Odpowiedzi:

8

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αMTαTα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 NASYNCαASYNCα,βASYNCαβ

d(α,β):=2N
Njest najwcześniejszym indeksem, w którym przejścia stanu w i β różnią się; w przeciwnym razie, jeśli α = β , definiujemy d ( α , β ) = 0 .αβα=βd(α,β)=0

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 ( α , βdASYNCdα,βASYNCd(α,β)=d(β,α)α,β,γASYNC utrzymuje się trywialnie, jeśli γ = α lub γ = β . Rozważmy teraz przypadek, że d ( α , γ ) d ( γ , β ) > 0 , tj. D ( α , γ ) = 2 - n 1 i d ( γ , βd(α,β)d(α,γ)+d(γ,β)γ=αγ=βd(α,γ)d(γ,β)>0d(α,γ)=2n1 , dla niektórych wskaźników n 1n 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(γ,β)=2n2n1n2γn21βn11ααβn1d(α,β)=d(α,γ)i następuje nierówność trójkąta. Przypadek, w którym następuje analogicznie.0<d(α,γ)<d(γ,β)

dϵBε(α)={βASYNCd(α,β)<ε}αSASYNCαSNβNαSαSN0βASYNCd(α,β)<2N,αβNβSS

[1] James Munkres. Topologia

Piotr
źródło
Dzięki za odpowiedź. Muszę się nad tym zastanowić. Nawiasem mówiąc, czy mówisz o książce „Topologia” Jamesa R. Munkresa, kiedy to mówisz The metric d induces a topology (e.g., page~119 of [1]) where the ϵ-balls...?
hengxin
Tak, dodałem referencję.
Peter
Zauważyłem, że zasugerowałeś zmianę tytułu tego postu (jeśli popełniłem błąd, zignoruj ​​ten komentarz). Przede wszystkim zgadzam się, że dwa podproblemy powinny znaleźć odzwierciedlenie w tytule. Nie pytam jednak: „ dlaczego linearyzowalność jest właściwością bezpieczeństwa?”. Pytam o konsekwencje tego faktu. Nie jestem pewien, jak odpowiednio zmienić tytuł i pominąłem tę modyfikację. Daj mi znać, jeśli masz inne uwagi lub pomysły.
hengxin
Uświadomiłem sobie, że charakterystyka (dowód) linearyzowalności jako zbioru zamkniętego w zasadzie nie ma nic wspólnego z pojęciem punktów linearyzacji. Wydaje się, że jest to bardziej ogólny dowód, który charakteryzuje każdą właściwość bezpieczeństwa jako zamknięty zestaw. Przegapiłem coś?
hengxin
Tak, wszystkie właściwości bezpieczeństwa są zestawami zamkniętymi, podczas gdy właściwości żywotności są gęstymi zestawami w tej topologii. W rzeczywistości każdą właściwość (tj. Zestaw przebiegów) można wyrazić jako koniunkcję (tj. Przecięcie) właściwości bezpieczeństwa i żywotności.
Peter
6

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.

Shaull
źródło
u¨
Jestem prawie pewien, że Iv'e widział artykuły, które zajmują się linearyzacją przez LTL, przynajmniej w szczególnych przypadkach. Jeśli je znajdę, skomentuję.
Shaull
To będzie świetne. Zawsze jestem ciekawy, jak radzić sobie z linearyzacją przez LTL, zwłaszcza z pojęciem punktów linearyzacji. Podążając za twoją wskazówką, znajduję artykuł Udowadniający liniowość za pomocą logiki czasowej . Spróbuję to przeczytać w tych dniach. Nie jestem jednak pewien jego jakości. Czekam na twoje komentarze.
hengxin
Być może to będzie miało zastosowania. Sądząc po autorach, jest to poważny artykuł. Nie jestem jednak pewien, jak ścisłe jest połączenie z LTL.
Shaull