Bezpečná sémantika - Safe semantics

Bezpečná sémantika je počítačový hardware model konzistence. Popisuje jeden typ záruky, že a datový registr poskytuje, když je sdílena několika procesory v paralelní počítač nebo v síti počítačů spolupracujících.

Dějiny

Bezpečná sémantika byla poprvé definována pomocí Leslie Lamport v roce 1985.[1] Formálně to bylo definováno v Lamportově „Komunikaci mezi procesy“ v roce 1986.[2]

Bezpečný registr byl implementován v mnoha distribuovaných systémech.

Popis

Bezpečná sémantika je definována pro proměnnou s jedním zapisovačem, ale s více čtečkami (SWMR). Registr SWMR je bezpečný, pokud každá operace čtení splňuje tyto vlastnosti:

Bezpečný registr - žádné překrývání
  1. Operace čtení, která není souběžná s žádnou operací zápisu, vrací hodnotu zapsanou poslední operací zápisu.
  2. Operace čtení, která je souběžná s operací zápisu, může vrátit jakoukoli hodnotu v povoleném rozsahu hodnot registru (například 0,1,2, ...).
    bezpečné překrývání registrů

Zejména vzhledem k souběžnosti operace čtení a zápisu může čtení vracet hodnotu, která nebyla zapsána zápisem. Návratová hodnota musí patřit pouze doméně registru.

Binární bezpečný registr lze považovat za modelování trochu blikajícího. Bez ohledu na předchozí hodnotu registru může jeho hodnota blikat, dokud zápis nebude dokončen. Proto čtení, které se překrývá se zápisem, může vrátit 0 nebo 1.

Máselnice označuje vstup a výstup serverů do / z distribuovaného systému. Baldoni a kol. ukázat, že žádný registr nemůže mít silnější vlastnost pravidelná sémantika v synchronní systém za nepřetržitého churn.[3] Bezpečný registr však lze implementovat za nepřetržitého churn v nesynchronním systému.[4] Modelování a implementace typu úložné paměti (Safe Register) za klidového churn vyžaduje některé systémové modely, jako jsou klientské a serverové systémy.[4] Klientské systémy obsahují konečný, libovolný počet procesů, které jsou odpovědné za čtení a zápis do systému serveru. Systém serveru však musí zajistit, aby operace čtení a zápisu probíhaly správně.

Implementace

Implementace bezpečného registru zahrnuje:

Bezpečný registr je udržován sadou aktivních serverů.

Klienti neudělají žádné informace z registru.

Nakonec synchronní systém

Quora (sada serverových nebo klientských systémů)

Velikost operace čtení a zápisu prováděné na quora = n - f - J (n je počet serverů, J je počet serverů, které vstupují a opouštějí, a f je počet serverů Byzantské neúspěchy.

Algoritmy, jako je spojení, čtení a zápis.[4]

Připojit se

Server (si), který chce vstoupit do systému serveru, vysílá dotazovací zprávu na jiné servery, aby je informoval o svém vstupu, si vyžádá aktuální hodnotu registru. Jakmile jiný server obdrží tento dotaz, pošlou odpovědi na si. Poté, co si přijme dostatek odpovědí z jiných serverů, shromáždí odpovědi a uloží je do sady odpovědí. Si čeká, až získá dostatek odpovědí (n-f-j) z jiných serverů, pak vybere nejčastěji přijímanou hodnotu. Si také:

  • Aktualizuje svou místní kopii registru
  • Stává se aktivní
  • Odpovědi na procesy v sadě odpovědí
  • Pokud se stane aktivním, odešle odpovědi na ostatní servery. Jinak uloží dotazy a odpoví, až bude aktivní.
  • Když získá odpovědi z jiných serverů, přidá novou odpověď do sady odpovědí a zahodí starou hodnotu.
  • Pokud je hodnota odpovídajícího serveru větší než hodnota si, si si zachová novou hodnotu.

Číst

Algoritmus čtení je základní verzí spojení. Rozdíl je v vysílacím mechanismu používaném operací čtení. Klient (cw) vysílá zprávu do systému a jakmile server obdrží požadavek, odešle klientovi odpověď. Jakmile klient obdrží dostatek odpovědí (n-f-j), přestane posílat dotaz.

operace čtení

Psát si

Klient (cw) odešle dotaz do systému v různých kolech a počká, až obdrží dvě potvrzení. (sn = pořadové číslo)

operace zápisu
operace zápisu

Důvodem pro přijetí dvou potvrzení je vyhnout se nebezpečí v systému. Když proces odešle potvrzení (ack), může zemřít po jedné milisekundě. Klient proto neobdrží žádné potvrzení.

Platnost bezpečného registru (pokud čtení není souběžné s žádným zápisem, vrací poslední zapsanou hodnotu) byla prokázána na základě systému kvora.[4] Vzhledem ke dvěma systémům kvora (Qw, Qr) Qw označuje servery, které vědí o nejnovější hodnotě, a Qr označuje hodnoty čtených odpovědí. Velikost každého kvora se rovná n-f-j.[4] Prokázání platnosti bezpečného registru vyžaduje prokázání

byly B je počet byzantských neúspěchů.

Důkaz: Červená oblast označuje (Qw∩Qr) B a modrá oblast označuje Qr∩B. Z předpokladu je velikost každého kvora n-f-j, takže červená oblast má aktivní servery n-3f-2j. Proto,

je přísně větší než f.

platnost

Poznámky

  1. ^ Lamport, Leslie (červen 1986). „O meziprocesové komunikaci: Část I: Základní formalismus“ (PDF). Distribuované výpočty. 1 (2): 77–85. doi:10.1007 / BF01786227. ISSN  0178-2770.
  2. ^ Lamport, Leslie (červen 1986). "O meziprocesové komunikaci: Část I: Základní formalismus". Distribuované výpočty. 1 (2): 77–85. doi:10.1007 / BF01786227. ISSN  0178-2770.
  3. ^ Baldoni, Roberto; Bonomi, Silvia; Raynal, Michel (leden 2012). "Implementace pravidelného registru v eventuálně synchronním distribuovaném systému náchylném k nepřetržitému churn". Transakce IEEE na paralelních a distribuovaných systémech. 23 (1): 102–109. doi:10.1109 / TPDS.2011.97. ISSN  1045-9219.
  4. ^ A b C d E Baldoni, Roberto; Bonomi, Silvia; Nezhad, Amir Soltani (listopad 2013). „Protokol pro implementaci byzantského úložiště v distribuovaných systémech náchylných k víření“. Teoretická informatika. 512: 28–40. doi:10.1016 / j.tcs.2013.04.005.

Viz také