Mengapa linierabilitas merupakan properti keselamatan dan mengapa properti keselamatan ditutup?

Dalam Bab 13 "Objek Atom" dari buku "Algoritma Terdistribusi" oleh Nancy Lynch, linearitas (juga dikenal sebagai atomisitas) terbukti menjadi properti yang aman. Dengan kata lain, properti jejak yang sesuai adalah nonempty, prefix-closed, dan limit-closed , sebagaimana didefinisikan dalam Bagian 8.5.3. Secara tidak resmi, properti keselamatan sering diartikan sebagai mengatakan bahwa sesuatu yang "buruk" tidak pernah terjadi.

Berdasarkan ini, masalah pertama saya adalah sebagai berikut:

Apa keuntungan dari linierisasi sebagai properti keamanan? Apakah ada beberapa hasil berdasarkan fakta ini dalam literatur?

Dalam studi klasifikasi properti keamanan dan properti liveness, telah diketahui bahwa properti keamanan dapat dikategorikan sebagai set tertutup dalam topologi yang sesuai. Dalam makalah "Klasifikasi Keselamatan-Kemajuan" @ 1993 oleh Amir Pnueli et al. , topologi metrik diadopsi. Lebih khusus, properti adalah serangkaian kata (terbatas atau tak terbatas) di atas alfabet Σ . Properti A ( Φ ) terdiri dari semua kata-kata yang tak terbatas σ sehingga semua prefiks dari σ milik Φ . Misalnya, jika Φ = a + b ∗ , maka$\Phi$$\Sigma$$A(\Phi)$$\sigma$$\sigma$$\Phi$$\Phi = a^{+}b^{\ast}$ . Properti infinitary Π didefinisikansebagai properti keamananjika Π = A ( Φ ) untuk beberapa properti fital Φ . Metrik d ( σ , σ ′ ) antara kata tak hingga σ dan σ ′ didefinisikan sebagai 0 jika identik, dan d ( σ , σ ′ ) = 2 $A(\Phi) = a^{\omega} + a^{+}b^{\omega}$$\Pi$$\Pi = A(\Phi)$$\Phi$$d(\sigma, \sigma')$$\sigma$$\sigma'$ sebaliknya, di manajadalah panjang awalan umum terpanjang yang mereka sepakati. Dengan metrik ini, properti keselamatan dapat dikarakterisasi sebagai perangkat tertutup secara topologi.$d(\sigma, \sigma') = 2^{-j}$$j$

Inilah masalah kedua saya:

Bagaimana mengkarakterisasi linearizablity sebagai set tertutup secara topologis? Secara khusus, apa yang mendasarinya dan apa topologi itu?

Apa keuntungan dari linierisasi sebagai properti keamanan? Apakah ada beberapa hasil berdasarkan fakta ini dalam literatur?

Misalkan Anda telah mengimplementasikan mesin memori bersama yang hanya memenuhi linierisasi akhirnya , didefinisikan sebagai berikut: dalam setiap proses α dari M , ada beberapa titik waktu T α , sehingga linierisasi bertahan sejak waktu T α aktif. Perhatikan bahwa tidak ada batas atas T . (*) (Ini adalah tiruan live buatan dari definisi sifat keselamatan linier dari kelakuan linier.)$M$$\alpha$$M$$T_\alpha$$T_\alpha$$T$

Implementasi memori bersama seperti itu tidak akan sangat berguna bagi programmer: Perhatikan bahwa jika hanya kelanjutan linieritas yang berlaku, tidak ada jaminan apa pun tentang konsistensi operasi baca / tulis dalam awalan "awal" apa pun dari suatu run (sebelum waktu yang tidak diketahui) ). Atau, dengan kata lain, apa pun yang terjadi sampai sekarang, Anda masih dapat memperpanjang awalan saat ini dari lari ke yang memenuhi linearitas akhirnya. $T$

(*) Jika ada batas atas seperti itu, maka linearitas akhirnya akan menjadi properti keselamatan.

Bagaimana mengkarakterisasi linearizablity sebagai set tertutup secara topologis? Secara khusus, apa yang mendasarinya dan apa topologi itu?

Kita dapat mendefinisikan topologi metrik pada himpunan , yang merupakan himpunan semua proses yang mungkin dari algoritma terdistribusi. Perhatikan bahwa setiap proses α ∈ A S Y N C sesuai dengan urutan transisi keadaan yang tak terbatas. Untuk α , β ∈ A S Y N C , α ≠ β , kami mendefinisikan d ( α , β ) : = 2 - N di mana $ASYNC$$\alpha \in ASYNC$$\alpha, \beta \in ASYNC$$\alpha \ne \beta$

Kami pertama berpendapat bahwa adalah metrik pada A S Y N C . Menurut definisi, d adalah nonnegatif dan ∀ α , β ∈ A S Y N C kita memiliki d ( α , β ) = d ( β , α ) . Untuk α , β , γ ∈ A S Y N C , segitiga-ketimpangan d ( α , $d$$ASYNC$$d$$\forall \alpha,\beta \in ASYNC$$d(\alpha,\beta)=d(\beta,\alpha)$$\alpha,\beta,\gamma \in ASYNC$ dianggap sepele jika γ = α atau γ = β . Sekarang perhatikan kasus bahwa d ( α , γ ) ≥ d ( γ , β ) > 0 , yaitu, d ( α , γ ) = 2 - n 1 dan 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}$ , untuk beberapa indeks n 1 ≤ n 2 . Karena γ berbagi awalan umum panjang n 2 - 1 dengan β tetapi hanya awalan panjang n 1 - 1 dengan α , maka α dan β berbeda pada indeks n 1 , dan dengan demikian 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)$dan segitiga-ketidaksetaraan mengikuti. Kasus di mana mengikuti secara analog.$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. Topologi.

Mengenai pertanyaan pertama Anda - sifat-sifat keamanan, dengan cara tertentu, sifat-sifat "paling mudah" untuk ditangani, berkenaan dengan masalah-masalah seperti pengecekan model dan sintesis.

Alasan dasar untuk ini adalah bahwa dalam pendekatan automata-theoretik untuk metode formal, alasan tentang sifat keamanan berkurang menjadi alasan tentang jejak yang terbatas, yang lebih mudah daripada pengaturan jejak tak terbatas standar.

Lihatlah karya Orna Kupferman di sini sebagai titik awal.