安全性-活性分解定理とその関連研究 #wsa研 / Web System Architecture Society 7th

第 7 回 Web System Architecture 研究会で使用したスライドです。

本セッションでは、安全性-活性分解 (safety-liveness decomposition) と呼ばれる一連の結果について解説する。安全性-活性分解は、システムの仕様が与えられた時、それを安全性 (safety) および活性 (liveness) と呼ばれる、よりシンプルな特徴付けを持つクラスに分解して扱うための方法論である。さらにセッションの後半では、安全性と活性の組み合わせ以外にも提案されている派生的な特徴付けについても述べる。

イベント概要：https://wsa.connpass.com/event/187128/
ブログ記事：https://ccvanishing.hateblo.jp/entry/2020/11/14/214355

Transcript

1. ҆શੑ-׆ੑ෼ղఆཧͱͦͷؔ࿈ݚڀ νΣγϟೣ (@y_taka_23) November 13, 2020 ୈ 7 ճ Web System Architecture ݚڀձ
2. ΞδΣϯμ ҆શੑͱ׆ੑ ෼ղఆཧ ͦͷଞͷఆࣜԽ ·ͱΊ 2 / 16
3. ҆શੑͱ׆ੑ
4. Web γεςϜͱܗࣜख๏ • ܗࣜख๏ (formal methods) • γεςϜ΍ϓϩάϥϜΛ਺ֶతର৅ʹΑΓදݱɾݕࠪ • ໢ཏతͳςετέʔε͕࡞੒Ͱ͖ͳ͍ঢ়گͰҖྗΛൃش • Web γεςϜʹ͓͚Δܗࣜख๏ͷར༻ • ࠶ݱ͕೉͍͠λΠϛϯά΍ނো͕ΒΈͷόά͕ݕࠪͰ͖Δ • ෼ࢄγεςϜͷຽओԽʹ൐͍࠾༻ࣄྫ͕༂ਐ • Ϋϥ΢υϕϯμʔ: AWS(S3, DynamoDB), Azure(CosmosDB) • ϛυϧ΢ΣΞ OSS: CockroachDB, TiDB, elasticsearch • ϞόΠϧΞϓϦ: FINAL FANTASY XV POCKET EDITION 3 / 16
5. γεςϜͷ࢓༷هड़ ྫ (૬ޓഉଞ) ΫϦςΟΧϧηογϣϯΛཁٻ͢Δϓϩηε͕ೋͭɺฒߦͯ͠ಈ࡞͍ͯ͠Δͱ ͢Δɻ͜ͷͱ͖ຬͨ͞ΕΔ΂͖࢓༷͸Կ͔ʁ • ೋͭͷϓϩηε͕ಉ࣌ʹΫϦςΟΧϧηογϣϯʹೖΒͳ͍ • ͲͪΒͷϓϩηε΋͍ͣΕΫϦςΟΧϧηογϣϯʹೖΔ • લऀ͚ͩͩͱʮԿ΋͠ͳ͍ʯ΋࢓༷Λຬͨͯ͠͠·͏ 4 / 16
6. ҆શੑͱ׆ੑͷ௚ײతͳҙຯ ఆٛ • ʮѱ͍͜ͱ͕ܾͯ͠ى͜Βͳ͍ੑ࣭ʯΛ҆શੑ (safety) ͱݺͿ • ʮྑ͍͜ͱ͕͍ͣΕى͜Δੑ࣭ʯΛ׆ੑ (liveness) ͱݺͿ • ࢓༷Λهड़͢Δʹ͸ɺ҆શੑͱ׆ੑ͸ඞͣ྆ํඞཁʹͳΔ • ҆શੑ͸ଟ͘ͷ৔߹ɺ1 εςοϓ࣮ߦͷલޙͷؔ܎͔Βূ໌Ͱ͖Δ • ׆ੑ͸ԿΒ͔ͷ஋͕୯ௐʹݮগ͠༗ݶճͰఈΛಥ͘͜ͱΛূ໌͢Δඞཁ͕ ͋Δ 5 / 16
7. ݕࠪͷ௚ײతͳΠϝʔδ • X: γεςϜͷঢ়ଶΛແ࡞ҝʹܨ͛ͨແݶྻશମ • Y ⊂ X: γεςϜ͕࣮ࡍʹ௨ա͠͏Δແݶྻͷશମ • P: ࢓༷Λຬ͍ͨͯ͠Δແݶྻͷશମ • Y ⊂ P ͳΒ࢓༷͸ຬͨ͞Ε͍ͯΔ 6 / 16
8. ύε͕ͳ͢ڑ཭ۭؒ ఆٛ S Λঢ়ଶͷू߹ͱͨ͠ͱ͖ Sω ͷݩΛύεͱݺͿ ఆٛ ύε π1 = {ai } ͱ π2 = {bi } ʹରͯ͠ d(π1 , π1 ) = 0 d(π1 , π2 ) = 1/2min{i∈N:ai̸=bi} ͱఆΊΔɻd(π1 , π2 ) ͸ Sω ্ͷڑ཭ͱͳΔ 7 / 16
9. Ґ૬ʹΑΔಛ௃෇͚ ఆٛ (Alpern-Schneider, 1985) ύεશମ͔ΒͳΔҐ૬ۭؒʹ͓͍ͯɺͦͷ෦෼ू߹Λੑ࣭ (property) ͱݺͿɻ ಛʹดू߹Λ҆શੑɺ᜚ີू߹Λ׆ੑͱݺͿ • P ͕ดͰ͋Δͱ͸ɺP ʹଐ͞ͳ͍೚ҙͷ఺ x ʹରͯ͠ɺx ͷे෼ۙ͘ͷ఺ ͸΍͸Γ P ʹଐ͞ͳ͍ͱ͍͏͜ͱ • P ͕᜚ີͰ͋Δͱ͸ɺ೚ҙͷ఺͕ P ͷ఺Λ༻͍ͯແݶʹߴ͍ਫ਼౓ͰۙࣅͰ ͖Δͱ͍͏͜ͱ 8 / 16
10. ดू߹ͱ᜚ີू߹ ྫ ࣮਺શମ͕ͳ͢ू߹ R ʹ௨ৗͷڑ཭ͰҐ૬Λఆٛ͢Δͱ • ด۠ؒ [0, 1] ͸ดू߹ • ༗ཧ਺શମ͕ͳ͢ू߹ Q ͸᜚ີू߹ ྫ ࡾछྨͷঢ়ଶ a, b, c ͷΈ͔ΒͳΔγεςϜΛߟ͑ͨͱ͖ • a ͱ b ͕ަޓʹݱΕΔΑ͏ͳύεͷશମ͸ดू߹ • c ͕ແݶճݱΕΔΑ͏ͳύεͷશମ͸᜚ີू߹ 9 / 16
11. ෼ղఆཧ
12. ෼ղఆཧ ఆཧ (Alpern-Schneider, 1985) ೚ҙͷੑ࣭ P ʹରͯ͠ɺ҆શੑ S ͱ׆ੑ L ͕ଘࡏͯ͠ P = S ∩ L • ͭ·Γ೚ҙͷੑ࣭͸ʮ͋Δ҆શੑΛຬͨ͢΋ͷʯ͔ͭʮ͋Δ׆ੑΛຬͨ͢΋ ͷʯͱ͍͏ܗͰදݱͰ͖Δ • ͦΕͧΕʹύʔτʹઐ༻ͷ࠷దԽΞϧΰϦζϜΛద༻Ͱ͖Δ 10 / 16
13. Büchi ΦʔτϚτϯʹର͢Δ෼ղఆཧ ఆཧ (Alpern-Schneider, 1987) ೚ҙͷن໿ Büchi ΦʔτϚτϯ m ʹରͯ͠ɺBüchi ΦʔτϚτϯ Safe(m) ͱ Live(m) ΁ͷม׵खଓ͖͕ଘࡏ͠ɺ L(m) = L(Safe(m)) ∩ L(Live(m)) ͞Βʹ L(Safe(m)) ͸ดू߹ɺL(Live(m)) ͸᜚ີू߹ͱͳΔ • ͭ·Γ Büchi ΦʔτϚτϯͰදͤΔੑ࣭͸෼ղʹ͍ͭͯด͍ͯ͡Δ • ͔ͭͦͷ෼ղ͸ߏ੒తʹ༩͑ΒΕΔ 11 / 16
14. ઢܗ࣌૬࿦ཧࣜʹର͢Δ෼ղఆཧ ఆཧ (Maretić-Dashti-Basin, 2014) ೚ҙͷઢܗ࣌૬࿦ཧࣜ φ ʹରͯ͠ɺઢܗ࣌૬࿦ཧࣜ σ ͱ λ ͕ଘࡏ͠ɺ φ = σ ∧ λ ͞Βʹ L(σ) ͸ดू߹ɺL(λ) ͸᜚ີू߹ͱͳΔ • ͭ·Γઢܗ࣌૬࿦ཧࣜͰදͤΔੑ࣭΋෼ղʹ͍ͭͯด͍ͯ͡Δ • ઢܗ࣌૬࿦ཧࣜ͸ counter-free ͳ Büchi ΦʔτϚτϯͱ౳Ձ 12 / 16
15. ϙΠϯτͱͳΔิ୊ ิ୊ Ґ૬ۭؒͷ೚ҙͷ෦෼ू߹ P ʹରͯ͠ɺดแΛ ⌈P⌉ɺิू߹Λ P Ͱද͢ͱ P = ⌈P⌉ ∩ ( ⌈P⌉ ∪ P ) ͳ͓ ⌈P⌉ ͸ดू߹ɺ⌈P⌉ ∪ P ͸᜚ີू߹ͱͳΔ • ͭ·Γ͋ΔΫϥεʹؔ͢Δ෼ղఆཧΛࣔ͢ʹ͸ɺͦͷΫϥε͕ ⌈·⌉ɺ·, ∪ ʹ ͍ͭͯด͍ͯ͡Δ͜ͱΛࣔͤ͹Α͍ 13 / 16
16. ௚ײతͳཧղ 14 / 16
17. ͦͷଞͷఆࣜԽ
18. ͦͷଞͷఆࣜԽ • ଋΛ༻͍ͨҰൠԽ (Manolios-Trefler, 2003) • ଋ্ͷॱংอଘ͔ͭႈ౳ͳ֦େ࡞༻ૉͰ҆શੑͱ׆ੑΛఆٛ • Ґ૬ʹΑΔఆٛͷਅͷҰൠԽʹͳ͍ͬͯΔ • ෼ذ࣌ؒత (branching-time) ͳϞσϧ΁ͷద༻ • ֊૚తͳ෼ྨ (Chang-Manna-Pnueli, 1993) • ดू߹ɺ։ू߹ɺGδ ू߹ɺFσ ू߹ • ௚ײతͳҙຯ෇͚ͱΑ͘ରԠͨ͠֊૚ߏ଄ • ֤֊૚ʹରͯ͠෼ղఆཧͷྨࣅ͕੒Γཱͭ 15 / 16
19. ·ͱΊ
20. ·ͱΊ • Web γεςϜͱܗࣜख๏ • ੍ޚࠔ೉ͳ࣮ߦύεΛ໢ཏతʹݕࠪՄೳ • ۙ೥ɺಛʹ෼ࢄγεςϜͷݕূʹ࣮༻ྫ͋Γ • ೚ҙͷੑ࣭ͷ҆શੑͱ׆ੑ΁ͷ෼ղ • Ґ૬తͳಛ௃෇͚ɿ҆શੑ=ดू߹ɺ׆ੑ=᜚ີू߹ • ෼ղఆཧͷ೿ੜݚڀ • αϒΫϥεʹର͢Δ෼ղͷดੑ • ดू߹ɾ᜚ີू߹Ҏ֎Λ༻͍ͨҰൠԽ 16 / 16