የ Schrödinger ድመት ያለ ሳጥን፡ በተከፋፈሉ ስርዓቶች ውስጥ ያለው የጋራ መግባባት ችግር

እንግዲያውስ እናስብ። 5 ድመቶች በክፍሉ ውስጥ ተዘግተዋል, እና ባለቤቱን ለማንቃት, ሁሉም በዚህ ላይ አንድ ላይ መስማማት አለባቸው, ምክንያቱም በሩን መክፈት የሚችሉት በአምስቱ ላይ በመደገፍ ብቻ ነው. ከድመቶቹ አንዱ የሽሮዲንገር ድመት ከሆነ እና ሌሎች ድመቶች ስለ ውሳኔው የማያውቁ ከሆነ, ጥያቄው የሚነሳው "ይህን እንዴት ማድረግ ይችላሉ?"

በዚህ ጽሑፍ ውስጥ ስለ ዓለም የተከፋፈሉ ስርዓቶች ጽንሰ-ሀሳባዊ አካል እና ስለ ሥራቸው መርሆች ቀለል ባለ መልኩ እነግራችኋለሁ. እንዲሁም ከፓክሶሳ ስር ያለውን ዋናውን ሃሳብ በላይ ላይ አስቡበት።

ገንቢዎች የደመና መሠረተ ልማቶችን፣ የተለያዩ የውሂብ ጎታዎችን ሲጠቀሙ፣ ብዙ ቁጥር ያላቸው አንጓዎች ባሉበት ክላስተር ውስጥ ሲሠሩ፣ መረጃው ወጥነት ያለው፣ ደህንነቱ የተጠበቀ እና ሁልጊዜ የሚገኝ እንደሚሆን እርግጠኞች ናቸው። ግን ዋስትናዎቹ የት አሉ?

በእርግጥ, እኛ ያለን ዋስትናዎች የአቅራቢዎች ዋስትናዎች ናቸው. በሰነዱ ውስጥ እንደሚከተለው ተገልጸዋል: "ይህ አገልግሎት በጣም አስተማማኝ ነው, የተሰጠው SLA አለው, አይጨነቁ, ሁሉም ነገር እርስዎ እንደጠበቁት ይሰራጫሉ."

ከትልቅ ኩባንያዎች የተውጣጡ ብልህ አጎቶች ሁሉም ነገር ጥሩ እንደሚሆን ስላረጋገጡልን ምርጡን ማመን ይቀናናል። ጥያቄውን አንጠይቅም-ለምን ፣ በእውነቱ ፣ ይህ በጭራሽ ሊሠራ የሚችለው? ለእንደዚህ ዓይነቶቹ ስርዓቶች ትክክለኛ አሠራር ምንም ዓይነት መደበኛ ማረጋገጫ አለ?

በቅርቡ ሄጄ ነበር። የተከፋፈለ የኮምፒውተር ትምህርት ቤት እና በዚህ ጭብጥ በጣም ተነሳሳ። በትምህርት ቤት ውስጥ ያሉ ትምህርቶች ከኮምፒዩተር ስርዓቶች ጋር ከተያያዙት ነገሮች ሁሉ ይልቅ በሂሳብ ትንታኔ ውስጥ እንደ ክፍሎች ነበሩ። ነገር ግን በየቀኑ የምንጠቀምባቸው በጣም አስፈላጊዎቹ ስልተ ቀመሮች፣ ሳንጠራጠር፣ በአንድ ጊዜ የተረጋገጠው በዚህ መንገድ ነው።

አብዛኛዎቹ ዘመናዊ የተከፋፈሉ ስርዓቶች የፓክሶስ ስምምነት ስልተ ቀመር እና የተለያዩ ማሻሻያዎችን ይጠቀማሉ። በጣም ጥሩው ነገር ትክክለኛነቱ እና በመርህ ደረጃ የዚህ ስልተ-ቀመር መኖር የመቻል እድሉ በብዕር እና በወረቀት ብቻ መረጋገጡ ነው። በተመሳሳይ ጊዜ, በተግባር, ስልተ ቀመር በደመና ውስጥ እጅግ በጣም ብዙ በሆኑ አንጓዎች ላይ በሚሰሩ ትላልቅ ስርዓቶች ውስጥ ጥቅም ላይ ይውላል.

ቀጥሎ የሚብራራው የብርሃን ምሳሌ፡ የሁለት ጄኔራሎች ችግርየሙቀት መጨመርን እንመልከት የሁለት ጄኔራሎች ተግባር.

ሁለት ጦር አለን - ቀይ እና ነጭ። ነጭ ወታደሮች በተከበበችው ከተማ ውስጥ ይገኛሉ። በጄኔራሎች A1 እና A2 የሚመሩ ቀይ ወታደሮች በከተማው ሁለት ጎኖች ይገኛሉ. የቀይ ራሶች ተግባር ነጩን ከተማ ማጥቃት እና ማሸነፍ ነው። ሆኖም የእያንዳንዱ የቀይ ጄኔራል ጦር በተናጥል ከነጭ ሰራዊት ያነሰ ነው።

ለቀይ ራሶች የድል ሁኔታዎች፡ ሁለቱም ጄኔራሎች ከነጮች ላይ የቁጥር ጥቅም ለማግኘት በአንድ ጊዜ ማጥቃት አለባቸው። ይህንን ለማድረግ ጄኔራሎች A1 እና A2 እርስ በርስ መስማማት አለባቸው. ሁሉም በተናጥል ካጠቁ ቀይ ራሶች ይሸነፋሉ።

ለመደራደር ጄኔራሎች A1 እና A2 በነጩ ከተማ ግዛት በኩል እርስ በርስ መልእክተኞችን ሊልኩ ይችላሉ. መልእክተኛው በተሳካ ሁኔታ ተባባሪ ጄኔራል ሊደርስ ይችላል ወይም በጠላት ሊጠለፍ ይችላል. ጥያቄ፡- በቀይ ፀጉር ጀነራሎች መካከል (ከ A1 ወደ A2 እና በተቃራኒው ከ A2 ወደ A1 መልእክተኞችን የመላክ ቅደም ተከተል) መካከል እንደዚህ ያለ የግንኙነት ቅደም ተከተል አለ ፣ በሰዓት X ጥቃት ላይ ለመስማማት ዋስትና ተሰጥቷቸዋል። በዋስትና ሁለቱም ጄኔራሎች አጋር (ሌላ ጄኔራል) በተመደበው ጊዜ X ላይ ጥቃት እንደሚሰነዝሩ የማያሻማ ማረጋገጫ እንደሚኖራቸው መረዳት ተችሏል።

A1 መልእክተኛውን ወደ A2 በላከል እንበል፡- "ዛሬ በመንፈቀ ሌሊት እንጥቃት!" አጠቃላይ A1 ከጄኔራል A2 ማረጋገጫ ውጭ ማጥቃት አይችልም. ከ A1 የመጣው መልእክተኛ ከደረሰ፣ አጠቃላይ A2 ከመልእክቱ ጋር ማረጋገጫ ይልካል፡- "አዎ ዛሬ ነጮችን እንሙላ"። አሁን ግን ጄኔራል A2 መልእክተኛው ደረሰ ወይም አልደረሰም አያውቅም፣ ጥቃቱ በአንድ ጊዜ ለመሆኑ ዋስትና የለውም። አሁን አጠቃላይ A2 እንደገና ማረጋገጫ ያስፈልገዋል።

የእነርሱን ግንኙነት የበለጠ ከገለጽነው የሚከተለውን ይሆናል፡ የቱንም ያህል የመልእክት ልውውጥ ዑደቶች ቢኖሩ ለሁለቱም ጄኔራሎች መልእክቶቻቸው እንደደረሳቸው ዋስትና የሚሰጥበት መንገድ የለም (ከመልእክተኞቹ መካከል አንዱንም መጥለፍ እንደሚቻል በማሰብ)።

የሁለቱ ጄኔራሎች ችግር አስተማማኝ ያልሆነ ግንኙነት ያላቸው ሁለት አንጓዎች ያሉበት በጣም ቀላል የተከፋፈለ ስርዓት ትልቅ ማሳያ ነው። ስለዚህ ለመመሳሰል 100% ዋስትና የለንም። ስለ ተመሳሳይ ችግሮች በኋላ በጽሁፉ ውስጥ በትልቅ ደረጃ ብቻ.

የተከፋፈሉ ስርዓቶችን ጽንሰ-ሀሳብ ማስተዋወቅ

የተከፋፈለ ስርዓት መልእክት መለዋወጥ የሚችል የኮምፒዩተሮች ቡድን (ከዚህ በኋላ እንደ ኖዶች) ነው። እያንዳንዱ የግል መስቀለኛ መንገድ አንዳንድ ራሱን የቻለ አካል ነው። መስቀለኛ መንገድ በራሱ ስራዎችን ማከናወን ይችላል, ነገር ግን ከሌሎች አንጓዎች ጋር ለመገናኘት, መልዕክቶችን መላክ እና መቀበል ያስፈልገዋል.

መልእክቶች በተለይ እንዴት እንደሚተገበሩ ፣ ምን ዓይነት ፕሮቶኮሎች ጥቅም ላይ ይውላሉ - ይህ በዚህ አውድ ውስጥ እኛን አያስደስተንም። የተከፋፈለው ስርዓት አንጓዎች መልዕክቶችን በመላክ እርስ በእርስ መረጃ መለዋወጥ መቻላቸው አስፈላጊ ነው።

ትርጉሙ ራሱ በጣም የተወሳሰበ አይመስልም, ነገር ግን የተከፋፈለ ስርዓት ለእኛ አስፈላጊ የሚሆኑ በርካታ ባህሪያት እንዳሉት ያስታውሱ.

የተከፋፈሉ ስርዓቶች ባህሪያት

1. ተቀራራቢነት - በአንድ ጊዜ ወይም በስርዓቱ ውስጥ የውድድር ክስተቶች የመከሰት እድል. በተጨማሪም፣ እነዚህ ሁነቶች የተከሰቱበት ግልጽ ቅደም ተከተል እስካልመጣ ድረስ በሁለት የተለያዩ አንጓዎች ላይ የተከሰቱት ክስተቶች በአንድ ላይ ሊሆኑ እንደሚችሉ እንመለከታለን። እና አብዛኛውን ጊዜ አናደርግም።
2. ምንም ዓለም አቀፋዊ ሰዓት የለም. ዓለም አቀፋዊ የሰዓት እጦት ምክንያት ግልጽ የሆነ የክስተቶች ቅደም ተከተል የለንም። በሰዎች ተራ ዓለም ውስጥ እኛ ሙሉ በሙሉ ሰዓታት እና ጊዜ እንዳለን እንለማመዳለን። ወደ የተከፋፈሉ ስርዓቶች ሲመጣ ሁሉም ነገር ይለወጣል. እጅግ በጣም ትክክለኛ የሆኑት የአቶሚክ ሰዓቶች እንኳን ተንሳፋፊ ናቸው፣ እና ከሁለቱ ክስተቶች መካከል የትኛው እንደተከሰተ መለየት የማንችልባቸው ሁኔታዎች አሉ። ስለዚህ በጊዜም መታመን አንችልም።
3. የስርዓት አንጓዎች ገለልተኛ አለመሳካት. ሌላ ችግር አለ፡ የእኛ አንጓዎች ዘላለማዊ ስላልሆኑ ብቻ የሆነ ነገር ሊሳሳት ይችላል። ሃርድ ድራይቭ ሊሳካ ይችላል፣ በደመናው ውስጥ ያለው ቨርቹዋል ማሽን እንደገና ሊነሳ ይችላል፣ አውታረ መረቡ ብልጭ ድርግም ይላል እና መልዕክቶች ሊጠፉ ይችላሉ። ከዚህም በላይ አንጓዎች በሚሠሩበት ጊዜ ሁኔታዎች አሉ, ግን በተመሳሳይ ጊዜ በስርዓቱ ላይ ይሠራሉ. የመጨረሻው የችግሮች ክፍል የተለየ ስም እንኳን ተቀብሏል: ችግሩ የባይዛንታይን ጄኔራሎች. እንደዚህ አይነት ችግር ያለበት የተከፋፈለ ስርዓት በጣም ታዋቂው ምሳሌ Blockchain ነው. ግን ዛሬ ይህንን ልዩ የችግሮች ክፍል አንመለከትም። አንድ ወይም ከዚያ በላይ አንጓዎች ሊሳኩ በሚችሉባቸው ሁኔታዎች ላይ ፍላጎት እናደርጋለን።
4. በአንጓዎች መካከል የግንኙነት ሞዴሎች (የመልእክት ሞዴሎች). አንጓዎች መልዕክቶችን በመለዋወጥ እንደሚገናኙ አስቀድመን አውቀናል. ሁለት የታወቁ የመልእክት መላላኪያ ሞዴሎች አሉ፡ የተመሳሰለ እና ያልተመሳሰለ።

በተከፋፈሉ ስርዓቶች ውስጥ በአንጓዎች መካከል የግንኙነት ሞዴሎች

የተመሳሰለ ሞዴል - መልእክቱ ከአንዱ መስቀለኛ መንገድ ወደ ሌላው እንዲደርስ የተረጋገጠበት የተወሰነ የታወቀ ዴልታ እንዳለ በእርግጠኝነት እናውቃለን። ይህ ጊዜ ካለፈ እና መልእክቱ ካልደረሰ, መስቀለኛ መንገዱ አልተሳካም ማለት እንችላለን. በእንደዚህ ዓይነት ሞዴል ውስጥ, ሊተነበይ የሚችል የጥበቃ ጊዜ አለን.

ያልተመሳሰለ ሞዴል - ባልተመሳሰሉ ሞዴሎች ውስጥ, የጥበቃው ጊዜ የተወሰነ ነው ብለን እንገምታለን, ነገር ግን ምንም ጊዜ የለም ዴልታ ከዚያ በኋላ መስቀለኛ መንገድ አለመሳካቱን ማረጋገጥ ይቻላል. እነዚያ። ከአንድ መስቀለኛ መንገድ መልእክት የሚጠብቀው ጊዜ በዘፈቀደ ረጅም ሊሆን ይችላል። ይህ አስፈላጊ ፍቺ ነው, እና ስለ እሱ የበለጠ እንነጋገራለን.

በተከፋፈሉ ስርዓቶች ውስጥ የጋራ መግባባት ጽንሰ-ሐሳብ

የጋራ መግባባትን ጽንሰ-ሀሳብ በመደበኛነት ከመግለጽዎ በፊት እኛ የምንፈልገውን ሁኔታ ምሳሌ አስቡበት- የስቴት ማሽን ማባዛት.

አንዳንድ የተከፋፈለ ሎግ አለን። በሁሉም የተከፋፈለ ስርዓት አንጓዎች ላይ ወጥነት ያለው እና ተመሳሳይ መረጃ እንዲይዝ እንፈልጋለን። ከአንጓዎቹ አንዱ ወደ መዝገብ ቤት የሚጽፈውን አዲስ እሴት ሲያውቅ፣ ስራው ይህንን እሴት ለሁሉም አንጓዎች ማቅረብ በመሆኑ ምዝግብ ማስታወሻው በሁሉም ኖዶች ላይ እንዲዘመን እና ስርዓቱ ወደ አዲስ ወጥነት ያለው ሁኔታ ይቀየራል። በተመሳሳይ ጊዜ አንጓዎቹ እርስ በእርሳቸው መስማማታቸው አስፈላጊ ነው-ሁሉም አንጓዎች የታቀደው አዲስ እሴት ትክክል እንደሆነ ይስማማሉ, ሁሉም አንጓዎች ይህንን ዋጋ ይቀበላሉ, እና በዚህ ሁኔታ ውስጥ ብቻ ሁሉም ሰው አዲስ እሴት መመዝገብ ይችላል.

በሌላ አነጋገር: አንዳቸውም አንጓዎች የበለጠ ወቅታዊ መረጃ እንዳላቸው አልተቃወሙም, እና የታቀደው እሴት ትክክል አይደለም. በነጠላ ትክክለኛ ተቀባይነት ያለው ዋጋ ላይ በመስቀለኛ መንገድ እና በስምምነት መካከል ያለው ስምምነት በተከፋፈለ ስርዓት ውስጥ ያለው ስምምነት ነው. በመቀጠል, የተከፋፈለ ስርዓት ከዋስትና ጋር ስምምነት ላይ ለመድረስ የሚያስችሉ ስለ ስልተ ቀመሮች እንነጋገራለን.

በመደበኛነት፣ የጋራ መግባባት ስልተ ቀመር (ወይም በቀላሉ የጋራ ስምምነት ስልተ-ቀመር) እንደ አንዳንድ ተግባራት የተከፋፈለውን ስርዓት ከግዛት ሀ ወደ ግዛት B የሚወስድ ነው። ከዚህም በላይ ይህ ሁኔታ በሁሉም አንጓዎች ተቀባይነት ያለው ሲሆን ሁሉም አንጓዎች ሊያረጋግጡት ይችላሉ። እንደ ተለወጠ, ይህ ተግባር በመጀመሪያ እይታ ላይ እንደሚመስለው ጨርሶ ቀላል አይደለም.

የጋራ ስምምነት ስልተ ቀመር ባህሪያት

ስርዓቱ መኖሩ እንዲቀጥል እና ከግዛት ወደ ክፍለ ሀገር በሚደረገው ሽግግር ላይ የተወሰነ መሻሻል እንዲኖር የስምምነት ስልተ-ቀመር ሶስት ባህሪያት ሊኖሩት ይገባል።

1. ስምምነት - ሁሉም በትክክል የሚሰሩ አንጓዎች አንድ አይነት እሴት መውሰድ አለባቸው (በጽሁፎች ውስጥ ይህ ንብረት እንደ የደህንነት ንብረትም ይገኛል)። አሁን እየሰሩ ያሉት ሁሉም አንጓዎች (ከሥርዓት ውጪ ያልሆኑ እና ከቀሪው ጋር ግንኙነት የሌላቸው) ወደ ስምምነት መምጣት እና አንዳንድ የመጨረሻ የጋራ እሴትን መቀበል አለባቸው።

   እኛ የምናስበው በተከፋፈለው ስርዓት ውስጥ ያሉት አንጓዎች መስማማት እንደሚፈልጉ እዚህ መረዳት አስፈላጊ ነው. ይኸውም አሁን እየተነጋገርን ያለነው አንድ ነገር በቀላሉ ሊወድቅ ስለሚችልባቸው ሥርዓቶች ነው (ለምሳሌ፣ አንዳንድ መስቀለኛ መንገድ አይሳካም)፣ ነገር ግን በዚህ ሥርዓት ውስጥ በእርግጠኝነት ሆን ተብሎ በሌሎች ላይ የሚሠሩ አንጓዎች የሉም (የባይዛንታይን ጄኔራሎች ተግባር)። በዚህ ንብረት ምክንያት ስርዓቱ ወጥነት ያለው ሆኖ ይቆያል።

2. አቋምህን - ሁሉም በትክክል የሚሰሩ አንጓዎች ተመሳሳይ ዋጋ ካቀረቡ v, ስለዚህ እያንዳንዱ በትክክል የሚሰራ መስቀለኛ መንገድ ይህንን ዋጋ መቀበል አለበት v.
3. መጪረሻ - ሁሉም በትክክል የሚሰሩ አንጓዎች በመጨረሻ የተወሰነ እሴት (የህይወት ንብረት) ይወስዳሉ ፣ ይህም አልጎሪዝም በስርዓቱ ውስጥ እድገት እንዲኖር ያስችለዋል። በትክክል የሚሰራ እያንዳንዱ ግለሰብ መስቀለኛ መንገድ ፈጥኖም ሆነ ዘግይቶ የመጨረሻውን ዋጋ መቀበል እና ማረጋገጥ አለበት: "ለእኔ, ይህ ዋጋ እውነት ነው, ከጠቅላላው ስርዓት ጋር እስማማለሁ."

የጋራ ስምምነት ስልተ ቀመር እንዴት እንደሚሰራ የሚያሳይ ምሳሌ

እስካሁን ድረስ የአልጎሪዝም ባህሪያት ሙሉ በሙሉ ግልጽ ላይሆኑ ይችላሉ. ስለዚህ ፣ ሁሉም አንጓዎች እንደተጠበቀው የሚሰሩበት ፣ መልእክቶች የማይጠፉ እና ምንም የማይሰበሩበት (ይህ በእውነቱ ይከሰታል?) በተመሳሰለ የመልእክት መላላኪያ ሞዴል ባለው ስርዓት ውስጥ ቀላሉ የጋራ ስምምነት ስልተ ቀመር ምን ደረጃዎችን እንደሚያልፍ በምሳሌ እንገልፃለን።

1. ሁሉም የሚጀምረው በጋብቻ ጥያቄ (ፕሮፖዝ) ነው. አንድ ደንበኛ "መስቀለኛ 1" ከተባለው መስቀለኛ መንገድ ጋር ተገናኝቶ ግብይት ከጀመረ በኋላ አዲስ እሴት ወደ መስቀለኛ መንገድ - ኦ. ከአሁን በኋላ "ኖድ 1" እንጠራዋለን. አቀረበ. እንደ ፕሮፖሰር "ኖድ 1" አሁን አዲስ መረጃ እንዳለው መላውን ስርዓት ማሳወቅ አለበት, እና ወደ ሌሎች አንጓዎች ሁሉ መልእክት ይልካል: "እነሆ! "ኦ" የሚለውን ዋጋ ተቀብያለሁ, እና ልጽፈው እፈልጋለሁ! እባክህ "ኦ"ን በምዝግብ ማስታወሻህ ውስጥ እንደምትመዘግብ አረጋግጥ።

   

2. ቀጣዩ ደረጃ ለታቀደው እሴት (ድምጽ መስጠት) ድምጽ መስጠት ነው. ለምንድን ነው? ሌሎች አንጓዎች የበለጠ የቅርብ ጊዜ መረጃዎችን ተቀብለው ሊሆን ይችላል፣ እና በተመሳሳይ ግብይት ላይ ውሂብ አላቸው።

   
   
   መስቀለኛ መንገድ "ኖድ 1" ፕሮፖዛልን ሲልክ፣ ሌሎቹ አንጓዎች በዚህ ክስተት ላይ መረጃ ለማግኘት ምዝግብ ማስታወሻቸውን ይፈትሹ። ምንም ግጭት ከሌለ አንጓዎቹ ያስታውቃሉ፡- “አዎ፣ ለዚህ ​​ክስተት ሌላ ውሂብ የለኝም። የ'O' እሴት እኛ የሚገባን በጣም ወቅታዊ መረጃ ነው።"

   በሌላ በማንኛውም ሁኔታ, አንጓዎቹ ለ "ኖድ 1" ምላሽ ሊሰጡ ይችላሉ: "ስማ! በዚህ ግብይት ላይ የበለጠ የቅርብ ጊዜ መረጃ አለኝ። "ኦ" ሳይሆን የተሻለ ነገር ነው።

   በድምጽ መስጫ ደረጃ, አንጓዎቹ ወደ አንድ ውሳኔ ይመጣሉ: ሁሉም ተመሳሳይ እሴት ይቀበላሉ, ወይም ከመካከላቸው አንዱ በጣም የቅርብ ጊዜ መረጃ እንዳለው በመግለጽ ይቃወማል.

3. የምርጫው ዙር ስኬታማ ከሆነ እና ሁሉም ሰው የሚደግፍ ከሆነ ስርዓቱ ወደ አዲስ ደረጃ ይሸጋገራል - እሴቱን መቀበል (ተቀበል)። "ኖድ 1" ሁሉንም ምላሾች ከሌሎች አንጓዎች እና ሪፖርቶች ይሰበስባል: "ሁሉም ሰው 'O' በሚለው ዋጋ ተስማምቷል! አሁን "ኦ" አዲሱ ትርጉማችን እንደሆነ በይፋ አውጃለሁ፣ ለሁሉም አንድ ነው! በማስታወሻ ደብተርዎ ውስጥ ይፃፉ ፣ አይርሱ ። ወደ መዝገብህ ጻፍ!"

   

4. የተቀሩት አንጓዎች ለራሳቸው "O" የሚለውን ዋጋ እንደጻፉ ማረጋገጫ (ተቀባይነት ያለው) ይልካሉ, በዚህ ጊዜ ምንም አዲስ ነገር አልተቀበለም (የሁለት-ደረጃ ቁርጠኝነት ዓይነት). ከዚህ ወሳኝ ክስተት በኋላ, የተከፋፈለው ግብይት እንደተጠናቀቀ እንመለከታለን.
   

ስለዚህ በቀላል ጉዳይ ውስጥ ያለው የጋራ ስምምነት ስልተ ቀመር አራት ደረጃዎችን ያካትታል-ፕሮፖዝ ፣ ድምጽ መስጠት (ድምጽ መስጠት) ፣ መቀበል (መቀበል) ፣ የመቀበል ማረጋገጫ (ተቀባይነት)።

በተወሰነ ደረጃ ስምምነት ላይ መድረስ ካልቻልን ፣ የታቀደውን እሴት ለማረጋገጥ ፈቃደኛ ባለመሆናቸው በአንጓዎች የቀረበውን መረጃ ከግምት ውስጥ በማስገባት ስልተ-ቀመር እንደገና ይጀምራል።

በተመሳሰል ስርዓት ውስጥ የጋራ ስምምነት ስልተ ቀመር

ከዚያ በፊት, ሁሉም ነገር ለስላሳ ነበር, ምክንያቱም የተመሳሰለው የመልእክት መላላኪያ ሞዴል ነው. ነገር ግን በዘመናዊው ዓለም ሁሉንም ነገር በማይመሳሰል መልኩ ለማድረግ እንደምንጠቀም እናውቃለን። ተመሳሳይ ስልተ ቀመር ባልተመሳሰለ የመልእክት መላላኪያ ሞዴል ውስጥ እንዴት እንደሚሰራ ፣ከእኛ መስቀለኛ መንገድ ምላሽ ለማግኘት የሚቆይበት ጊዜ በዘፈቀደ ረጅም ሊሆን ይችላል ብለን እናምናለን (በነገራችን ላይ የመስቀለኛ መንገድ አለመሳካት መስቀለኛ መንገድ በሚሆንበት ጊዜ እንደ ምሳሌ ሊወሰድ ይችላል) በዘፈቀደ ረጅም ምላሽ መስጠት ይችላል).

አሁን የጋራ መግባባት ስልተ ቀመር በመርህ ደረጃ እንዴት እንደሚሠራ ካወቅን ፣ ጥያቄው እዚህ ደረጃ ላይ ለደረሱ ፈላጊ አንባቢዎች ነው-በ N ኖዶች ውስጥ ያልተመሳሰለ የመልእክት ሞዴል ባለው ስርዓት ውስጥ ምን ያህል አንጓዎች ወደ ታች መውረድ እንደሚችሉ እና ስርዓቱ አሁንም መግባባት ላይ መድረስ ይችላል። ?

ከአጥፊው በስተጀርባ ያለው ትክክለኛ መልስ እና ምክንያታዊነት።ትክክለኛው መልስ: 0. ባልተመሳሰለ ስርዓት ውስጥ አንድ አንጓ እንኳን ቢወድቅ ስርዓቱ መግባባት ላይ መድረስ አይችልም። ይህ አረፍተ ነገር በታዋቂው የኤፍኤልፒ ቲዎሬም (1985፣ ፊሸር፣ ሊንች፣ ፓተርሰን፣ በአንቀጹ መጨረሻ ላይ ከዋናው ጋር አገናኝ) ውስጥ ተረጋግጧል፡- “ቢያንስ አንድ መስቀለኛ መንገድ ካልተሳካ የተከፋፈለ መግባባት ላይ መድረስ አይቻልም።

ወንዶች, ከዚያ ችግር አለብን, ሁሉም ነገር ከእኛ ጋር የማይመሳሰል መሆኑን እንለማመዳለን. እና እዚህ ነው. እንዴት መኖር መቀጠል ይቻላል?

አሁን ስለ ቲዎሪ፣ ስለ ሂሳብ ተነጋግረናል። ከሒሳብ ቋንቋ ወደ እኛ - ኢንጂነሪንግ እየተተረጎመ "መግባባት ላይ መድረስ አይቻልም" ማለት ምን ማለት ነው? ይህ ማለት "ሁልጊዜ ሊደረስበት አይችልም" ማለትም. መግባባት የማይደረስበት ጉዳይ አለ። እና ይህ ጉዳይ ምንድን ነው?

ይህ በትክክል ከላይ የተገለጸውን የኑሮ ንብረት መጣስ ነው። የጋራ ስምምነት የለንም, እና ከሁሉም አንጓዎች ምላሽ በሌለንበት ሁኔታ ስርዓቱ ሊራመድ አይችልም (በተወሰነ ጊዜ ውስጥ ማቋረጥ አይችልም). ምክንያቱም ባልተመሳሰለ ስርዓት ውስጥ ሊተነበይ የሚችል የምላሽ ጊዜ የለንም እና መስቀለኛ መንገድ መውረዱን ወይም ምላሽ ለመስጠት ረጅም ጊዜ እንደሚወስድ ማወቅ አንችልም።

በተግባር ግን መፍትሄ ማግኘት እንችላለን። ውድቀቶች በሚሆኑበት ጊዜ የእኛ አልጎሪዝም ለረጅም ጊዜ እንዲሰራ ይፍቀዱ (ላልተወሰነ ጊዜ ሊሰራ ይችላል)። ነገር ግን በአብዛኛዎቹ ሁኔታዎች, አብዛኛዎቹ አንጓዎች በትክክል ሲሰሩ, በስርዓቱ ውስጥ እድገት ይኖረናል.

በተግባር፣ ከፊል የተመሳሰለ የግንኙነት ሞዴሎች ጋር እየተገናኘን ነው። ከፊል ማመሳሰል እንደሚከተለው ተረድቷል-በአጠቃላይ ሁኔታ, የማይመሳሰል ሞዴል አለን, ነገር ግን የአንድ የተወሰነ ጊዜ "የዓለም አቀፋዊ ማረጋጊያ ጊዜ" ጽንሰ-ሐሳብ በመደበኛነት ቀርቧል.

በጊዜ ውስጥ ያለው ጊዜ በዘፈቀደ ለረጅም ጊዜ ላይመጣ ይችላል, ግን አንድ ቀን መምጣት አለበት. ምናባዊው የማንቂያ ሰዓቱ ይደውላል፣ እና ከዚያ ጊዜ ጀምሮ መልእክቶቹ የሚደርሱበትን ጊዜ ዴልታ መተንበይ እንችላለን። ከዚህ ጊዜ ጀምሮ, ስርዓቱ ከተመሳሳይ ወደ ተመሳሳይነት ይለወጣል. በተግባር, ከእንደዚህ አይነት ስርዓቶች ጋር እንገናኛለን.

ፓክሶስ አልጎሪዝም የጋራ መግባባት ችግሮችን ይፈታል

ፓክስስ አንዳንድ አንጓዎች ሊሳኩ እስካልቻሉ ድረስ የጋራ መግባባት ችግርን በከፊል ለተመሳሰሉ ስርዓቶች የሚፈታ የአልጎሪዝም ቤተሰብ ነው። የፓክሶስ ደራሲ ነው። ሌዘር ላምፖርት. በ1989 የአልጎሪዝም መኖር እና ትክክለኛነት መደበኛ ማረጋገጫ አቅርቧል።

ነገር ግን ማስረጃው በምንም መልኩ ቀላል አልነበረም። የመጀመሪያው እትም የተለቀቀው በ 1998 (33 ገፆች) ብቻ ነው አልጎሪዝምን የሚገልጽ። እንደ ተለወጠ, ለመረዳት እጅግ በጣም አስቸጋሪ ነበር, እና በ 2001 ለጽሑፉ ማብራሪያ ታትሟል, 14 ገጾችን ወሰደ. የሕትመቶች ጥራዞች የተሰጡት በእውነቱ የጋራ መግባባት ችግር ቀላል እንዳልሆነ ለማሳየት ነው, እና ከእንደዚህ አይነት ስልተ ቀመሮች በስተጀርባ በጣም ብልህ የሆኑ ሰዎች ትልቅ ስራ አለ.

ሌስሊ ላምፓር ራሱ በንግግራቸው ውስጥ በሁለተኛው አንቀፅ-ማብራሪያ ውስጥ አንድ መግለጫ ፣ አንድ መስመር (የትኛውን አልገለጸም) ፣ በተለያዩ መንገዶች ሊተረጎም እንደሚችል መናገሩ ትኩረት የሚስብ ነው። እናም በዚህ ምክንያት, ብዙ ቁጥር ያላቸው ዘመናዊ የፓክሶስ አተገባበር በትክክል አይሰራም.

የፓክሶስ ስራ ዝርዝር ትንታኔ ከአንድ በላይ መጣጥፍ ይወስዳል ስለዚህ የአልጎሪዝምን ዋና ሀሳብ በአጭሩ ለማስተላለፍ እሞክራለሁ። በጽሑፌ መጨረሻ ላይ ባሉት አገናኞች ውስጥ በዚህ ርዕስ ላይ የበለጠ ለመጥለቅ የሚረዱ ቁሳቁሶችን ያገኛሉ።

በፓክሶስ ውስጥ ያሉ ሚናዎች

የፓክሶስ አልጎሪዝም ሚናዎች ጽንሰ-ሀሳብ አለው። ሶስት ዋና ዋናዎቹን ተመልከት (ከተጨማሪ ሚናዎች ጋር ማሻሻያዎች አሉ)

1. ሀሳብ ሰጪዎች (እንዲሁም ውሎች ሊኖሩ ይችላሉ፡ መሪዎች ወይም አስተባባሪዎች). እነዚህ ሰዎች ስለ አንዳንድ አዲስ ትርጉም ከተጠቃሚው የተማሩ እና የመሪነት ሚና የሚጫወቱ ናቸው። የእነሱ ተግባር ለአዲስ እሴት አንድ ዙር ፕሮፖዛል ማስጀመር እና የአንጓዎችን ተጨማሪ ድርጊቶች ማስተባበር ነው። ከዚህም በላይ ፓክሶስ በተወሰኑ ሁኔታዎች ውስጥ በርካታ መሪዎችን መኖሩን ይፈቅዳል.
2. ተቀባዮች (መራጮች). እነዚህ አንድ የተወሰነ እሴት ለመቀበል ወይም ላለመቀበል ድምጽ የሚሰጡ አንጓዎች ናቸው። የእነሱ ሚና በጣም አስፈላጊ ነው, ምክንያቱም ውሳኔው በእነሱ ላይ የተመሰረተ ነው-ከሚቀጥለው የስምምነት ስልተ-ቀመር በኋላ ስርዓቱ በምን ሁኔታ ላይ እንደሚሄድ (ወይም እንደማይሄድ).
3. ተማሪዎች. የስርዓቱ ሁኔታ ሲቀየር በቀላሉ የሚቀበሉ እና አዲስ ተቀባይነት ያለው እሴት የሚጽፉ አንጓዎች። ውሳኔ አይወስዱም, ውሂብ ብቻ ይቀበላሉ እና ለዋና ተጠቃሚው ሊሰጡ ይችላሉ.

አንድ መስቀለኛ መንገድ በተለያዩ ሁኔታዎች ውስጥ በርካታ ሚናዎችን ሊያጣምር ይችላል።

የኮረም ጽንሰ-ሐሳብ

ስርዓት እንዳለን እንገምታለን። N አንጓዎች. እና አብዛኛዎቹ F አንጓዎች ሊሳኩ ይችላሉ. የኤፍ ኖዶች ካልተሳኩ ቢያንስ ሊኖረን ይገባል። 2F+1 ተቀባይ አንጓዎች.

እኛ ሁል ጊዜም ፣ በጣም በከፋ ሁኔታ ውስጥ እንኳን ፣ “ጥሩ” ፣ በትክክል የሚሰሩ አንጓዎች እንዲኖረን ይህ አስፈላጊ ነው። ያውና ኤፍ + 1 የተስማሙ "ጥሩ" አንጓዎች, እና የመጨረሻው ዋጋ ተቀባይነት ይኖረዋል. አለበለዚያ የተለያዩ የአካባቢ ቡድኖች የተለያዩ ትርጉሞችን የሚወስዱበት እና በመካከላቸው መስማማት የማይችሉበት ሁኔታ ሊኖር ይችላል. ስለዚህ ድምጽን ለማሸነፍ ፍጹም አብላጫ ድምጽ ያስፈልገናል።

የፓክሶስ ስምምነት ስልተ ቀመር አጠቃላይ ሀሳብ

የፓክሶስ አልጎሪዝም ሁለት ትላልቅ ደረጃዎችን ይይዛል, እነሱም በተራው እያንዳንዳቸው በሁለት ደረጃዎች ይከፈላሉ.

1. ደረጃ 1 ሀ፡ ተዘጋጅ. በዝግጅት ደረጃ መሪው (ፕሮፖሰር) ሁሉንም አንጓዎች ያሳውቃል: - "አዲስ የድምፅ አሰጣጥ ደረጃ እየጀመርን ነው. አዲስ ዙር አለን። የዚህ ዙር ቁጥር n. አሁን ድምጽ መስጠት እንጀምራለን" እስካሁን ድረስ፣ የአዲሱን ዑደት መጀመሩን ብቻ ነው የሚዘግበው፣ ነገር ግን አዲሱን ዋጋ አይዘግብም። የዚህ ደረጃ ተግባር አዲስ ዙር መጀመር እና ልዩ ቁጥሩን ለሁሉም ሰው ማሳወቅ ነው። የክብ ቁጥሩ አስፈላጊ ነው, ከቀደምት መሪዎች ሁሉ ከቀደምት የድምፅ ቁጥሮች የበለጠ መሆን አለበት. በስርዓቱ ውስጥ ያሉ ሌሎች አንጓዎች የመሪው መረጃ ምን ያህል ትኩስ እንደሆነ ስለሚረዱ ለክብ ቁጥሩ ምስጋና ይግባው ። ምናልባት ሌሎች አንጓዎች ከብዙ በኋላ ባሉት ዙሮች የድምፅ አሰጣጥ ውጤት ስላላቸው በቀላሉ መሪውን ከጊዜው ኋላ እንዳለ ይነግሩታል።
2. ደረጃ 1 ለ፡ ተስፋ. የተቀባይ አንጓዎች የአዲሱን የድምፅ አሰጣጥ ደረጃ ቁጥር ሲያገኙ ሁለት ውጤቶች ሊኖሩ ይችላሉ፡
   • የአዲሱ ድምጽ ቁጥር n ተቀባይው ከተሳተፈባቸው ቀዳሚ ድምጾች ቁጥር ይበልጣል። ከዚያም ተቀባይው ከንግዲህ ከ n ባነሰ ቁጥር በማንኛውም ድምጽ እንደማይሳተፍ ለመሪው ቃል ይልካል. ተቀባዩ ለአንድ ነገር ድምጽ ከሰጠ (ማለትም በሁለተኛው ደረጃ ላይ የተወሰነ እሴትን ቀድሞውኑ ተቀብሏል) ፣ ከዚያ ተቀባይነት ያለው እሴት እና የተሳተፈበትን የድምፅ ቁጥር በገባው ቃል ላይ ያያይዙታል።
   • ያለበለዚያ ፣ ተቀባዩ ቀድሞውኑ ከፍተኛ ቁጥር ስላለው ድምጽ ካወቀ ፣ በቀላሉ የዝግጅት ደረጃውን ችላ ማለት እና ለመሪው ምላሽ አይሰጥም።
3. ደረጃ 2 ሀ፡ ተቀበል. መሪው ምልአተ ጉባኤው ምላሽ እስኪያገኝ መጠበቅ አለበት (በስርዓቱ ውስጥ ያሉት አብዛኛዎቹ አንጓዎች) እና የሚፈለጉት የምላሾች ብዛት ከተቀበሉ ለክስተቶች እድገት ሁለት አማራጮች አሉት።
   • አንዳንድ ተቀባዮች አስቀድመው ድምጽ የሰጡባቸውን እሴቶች አስገብተዋል። በዚህ ሁኔታ መሪው ከፍተኛ ቁጥር ካለው ድምጽ ዋጋውን ይመርጣል. ይህንን እሴት x እንጠራው እና ለሁሉም አንጓዎች እንደዚህ ያለ መልእክት እንልካለን፡- “ተቀበል (n፣ x)”፣ የመጀመሪያው እሴት ከራሱ የፕሮፖዝ ደረጃ የድምጽ መስጫ ቁጥር ሲሆን ሁለተኛው እሴት ሁሉም ሰው የተሰበሰበበት ነው፣ ማለትም። ለእሱ ዋጋ, በእውነቱ, ድምጽ እንሰጣለን.
   • ከተቀበሉት ውስጥ አንዳቸውም ቢላኩ ምንም አይነት እሴቶችን ካልላኩ ነገር ግን በዚህ ዙር ድምጽ ለመስጠት ቃል ገብተዋል, መሪው ለእራሳቸው እሴት ድምጽ እንዲሰጡ ሊጋብዝ ይችላል, ይህም እሱ መሪ የሆነበት ዋጋ. y እንበለው። ለሁሉም አንጓዎች የቅጹን መልእክት ይልካል፡- “ተቀበል (n፣y)”፣ ከቀዳሚው ውጤት ጋር በማመሳሰል።
4. ደረጃ 2 ለ፡ ተቀባይነት. በተጨማሪም ተቀባይ አንጓዎች "ተቀበል (...)" የሚለውን መልእክት ሲቀበሉ, ከመሪው ጋር ይስማማሉ (ለሁሉም አንጓዎች በአዲሱ ዋጋ እንደሚስማሙ ማረጋገጫ ይላኩ) አንዳንዶቹን (ሌላ) ቃል ካልገቡ ብቻ ነው. ከዙሩ ቁጥር ጋር በድምጽ መስጫ ለመሳተፍ መሪ n' > nአለበለዚያ የማረጋገጫ ጥያቄውን ችላ ይላሉ.

   አብዛኛዎቹ አንጓዎች መሪውን ከመለሱ እና ሁሉም አዲሱን እሴት ካረጋገጡ አዲሱ ዋጋ እንደተቀበለ ይቆጠራል። ሆራይ! ብዙዎቹ ካልተየቡ ወይም አዲሱን እሴት ለመቀበል ፈቃደኛ ያልሆኑ አንጓዎች ካሉ ሁሉም ነገር እንደገና ይጀምራል።

የፓክስስ አልጎሪዝም የሚሰራው በዚህ መንገድ ነው። እያንዳንዳቸው ደረጃዎች ብዙ ስውር ዘዴዎች አሏቸው ፣ እኛ በተግባር የተለያዩ ውድቀቶችን ፣ የበርካታ መሪዎችን ችግሮች እና ሌሎችንም አላጤንንም ፣ ግን የዚህ ጽሑፍ ዓላማ አንባቢውን በከፍተኛ ደረጃ የተሰራጨ ኮምፒተርን ዓለም ለማስተዋወቅ ብቻ ነው።

በተጨማሪም ፓክሶስ የዚህ ዓይነቱ ብቻ እንዳልሆነ ልብ ሊባል የሚገባው ነው, ሌሎች ስልተ ቀመሮች አሉ, ለምሳሌ, Raftግን ይህ ለሌላ መጣጥፍ ርዕስ ነው።

ለተጨማሪ ጥናት ወደ ቁሶች አገናኞች

ጀማሪ ደረጃ፡

• የተከፋፈለ መግባባት እንዴት ነው የሚሰራው?, Preethi Kasireddy, መካከለኛ ላይ ጦማር ጽሑፍ
• Paxos ቀላል አደረገ. ስለ እውነት, Adi Kancherla, መካከለኛ ላይ ጦማር ጽሑፍ
• ያልተማከለ ሀሳቦችኢታይ አብርሃም ብሎግ
• ማመሳሰል፣ ያልተመሳሰለ እና ከፊል ማመሳሰልኢታይ አብርሃም፣ ብሎግ መጣጥፍ

የሌስሊ ላምፖርት ደረጃ፡-

• ከአንድ የተሳሳተ ሂደት (ኤፍኤልፒ የማይቻል) ጋር የተከፋፈለ መግባባት አለመቻልፊሸር፣ ሊንች እና ፓተርሰን፣ የምርምር ወረቀት፣ 1985
• የትርፍ ጊዜ ፓርላማሌስሊ ላምፖርት፣ የምርምር ወረቀት፣ 1998
• Paxos ቀላል አደረገሌስሊ ላምፖርት፣ የምርምር ወረቀት፣ 2001

ምንጭ: hab.com