تم وصف بروتوكول إجماع ستيلار لأول مرة في مقال علمي لعام 2015 من إعداد David Mazier. هذا هو "النظام الفيدرالي للاتفاقية البيزنطية" ، والذي يسمح لشبكات الحوسبة اللامركزية دون قادة للوصول بشكل فعال إلى توافق في الآراء بشأن أي قرار. تستخدم شبكة الفوترة النجمية بروتوكول توافق النجوم (SCP) للحفاظ على سجل ثابت للمعاملات التي يراها جميع الأعضاء.

تعتبر بروتوكولات التوافق صعبة الفهم. SCP أبسط من معظمهم ، لكن لا يزال يشارك هذه السمعة - جزئيًا بسبب الفكرة الخاطئة بأن "التصويت الفيدرالي" ، الذي خصصه النصف الأول من المقالة العلمية ، هو SCP. لكن هذا ليس كذلك! هذه مجرد لبنة مهمة ، والتي يتم استخدامها في النصف الثاني من المقال لإنشاء بروتوكول إجماع ستيلار الفعلي .

في هذه المقالة ، وصفنا باختصار ما هو "نظام الاتفاقيات" ، وما الذي يمكن أن يجعله "بيزنطي" ، ولماذا جعل النظام البيزنطي "اتحاديًا". ثم نوضح إجراء التصويت الموحد الموضح في مقالة SCP ، وأخيراً نوضح بروتوكول SCP نفسه.

نظم الاتفاق

يسمح نظام الاتفاقيات لمجموعة من المشاركين بالتوصل إلى توافق في الآراء بشأن موضوع ما ، على سبيل المثال ، ما يمكن طلبه للغداء.

قمنا في Interstellar بتطبيق نظامنا لترتيب الطعام: نطلب ما يقوله مدير عملياتنا John. هذا هو نظام اتفاق بسيط وفعال. نحن جميعًا نثق في جون ونعتقد أنه كل يوم سيجد شيئًا مثيرًا للاهتمام ومغذي.

لكن ماذا لو أساء جون استغلال ثقتنا؟ يمكنه أن يقرر بمفرده أننا جميعًا يجب أن نصبح نباتيين. في غضون أسبوع أو أسبوعين ، من المحتمل أن نسقطه ونسلم السلطة إلى إليزابيث. لكنها فجأة تحب الأفوكادو بالأنشوجة وتعتقد أن الجميع يجب أن يصبحوا هكذا. السلطة تفسد. لذلك ، من الأفضل إيجاد طريقة أكثر ديمقراطية: طريقة للتأكد من مراعاة التفضيلات المختلفة ، مع ضمان نتيجة لا لبس فيها في الوقت المناسب حتى لا يأمر أحد الغداء أو خمسة أشخاص يضعون أوامر مختلفة ، أو تستمر المناقشة حتى المساء.

يبدو أن الحل بسيط: التصويت! لكن هذا انطباع مضلل. من سيجمع بطاقات الاقتراع ويبلغ عن النتائج؟ ولماذا يصدق الباقون ما يقوله؟ ربما يمكننا أولاً التصويت للزعيم الذي نثق به لقيادة التصويت - لكن من الذي سيقود هذا التصويت الأول ؟ ماذا لو لم نتمكن من الاتفاق على قائد؟ أو إذا وافقنا على ذلك ، فهذا القائد عالق في اجتماع أو يغادر لإجازة مرضية؟

تم العثور على مشاكل مماثلة في شبكات الكمبيوتر الموزعة. يجب أن يتفق جميع المشاركين أو العقد على بعض الحلول ، على سبيل المثال ، دوره هو تحديث الملف المشترك أو أخذ المهمة من قائمة انتظار المعالجة. في شبكة العملة المشفرة ، يتعين على العقد مرارًا اختيار كيفية ظهور القصة الكاملة من بين العديد من الإصدارات المحتملة التي تتعارض في بعض الأحيان. يمنح اتفاق الشبكة هذا المتلقي ضمانًا بأن العملة (أ) صالحة (غير مزيفة) و (ب) لم تنفق بعد في أي مكان آخر. ويضمن أيضًا أنه قادر على إنفاق العملات في المستقبل لأن المستلم الجديد سيحصل على نفس الضمانات لنفس الأسباب.

يجب أن يتسامح مع أي نظام مطابق في شبكة كمبيوتر موزعة: يجب أن يعطي نتائج متسقة ، على الرغم من الأخطاء ، مثل خطوط الاتصال البطيئة والعقد غير المستجيبة وترتيب الرسائل غير الصحيح. نظام الاتفاقات البيزنطية يقاوم بالإضافة إلى الأخطاء "البيزنطية": العقد التي توفر معلومات خاطئة ، سواء بسبب خطأ أو في محاولة متعمدة لتقويض النظام أو الحصول على بعض المزايا. تسمى المرونة "البيزنطية" - القدرة على الوثوق بقرار جماعي ، حتى لو كان بعض أعضاء المجموعة يكذبون أو لا يتبعون قواعد صنع القرار - مثل الجنرالات الإمبراطورية البيزنطية الذين حاولوا تنسيق الهجوم. أنتوني ستيفنز لديه وصف جيد .

فكر في مالك عملة تشفير أليس ، التي يجب أن تختار بين شراء الآيس كريم اللذيذ من بوب ودفع ديون كارول. ربما تريد أليس أن تدفع كليهما دفعة واحدة ، وأن تنفق العملة نفسها بطريقة احتيالية. للقيام بذلك ، يجب عليها إقناع كمبيوتر بوب بأنه لم يتم سداد العملة إلى كارول ، وإقناع كمبيوتر كارول بأن العملة لم تُدفع لبوب مطلقًا. يجعل نظام الاتفاقيات البيزنطية هذا مستحيلًا تقريبًا باستخدام شكل من حكم الأغلبية يسمى النصاب القانوني . ترفض العقدة في مثل هذه الشبكة التبديل إلى إصدار معين من السجل حتى ترى أن عددًا كافٍ من العقد النظيرة - يكتمل النصاب القانوني - توافق على هذا الانتقال. بمجرد حدوث ذلك ، سيشكلون كتلة انتخابية كبيرة بما يكفي لإجبار عقد الشبكة المتبقية على الموافقة على قرارهم. قد تجعل أليس بعض العقد مستلقية نيابة عنها ، ولكن إذا كانت الشبكة كبيرة بما يكفي ، فسيتم قمع محاولتها من خلال أصوات العقد الصادقة.

كم عدد العقد المطلوبة للنصاب؟ على الأقل ، أغلبية ، أو بالأحرى أغلبية مؤهلة ، لمكافحة الأخطاء والاحتيال. ولكن من أجل حساب الأغلبية ، تحتاج إلى معرفة إجمالي عدد المشاركين. في مكتب Interstellar أو في الانتخابات المحلية ، من السهل التعرف على هذه الأرقام. ولكن إذا كانت مجموعتك عبارة عن شبكة ضعيفة التعريف يمكن للعقد الدخول إليها والخروج منها كما هو مطلوب دون التنسيق مع المركز ، فأنت بحاجة إلى نظام إتفاقية بيزنطية فدرالية يمكن أن يحدد النصاب القانوني ليس من قائمة محددة سلفًا للعقد ، ولكن بشكل حيوي ، من قائمة دائمة التغير وغير مكتملة لقطة من العقد في وقت معين.

قد لا يبدو من الممكن إنشاء النصاب القانوني من حيث عقدة واحدة في شبكة واسعة النطاق ، ولكن هذا ممكن. قد يكفل هذا النصاب القانوني نتائج التصويت اللامركزي. توضح الورقة البيضاء لـ SCP كيفية القيام بذلك باستخدام إجراء يسمى التصويت الموحد .

لفارغ الصبر

تفاصيل بقية المقال التصويت الفيدرالي وبروتوكول الإجماع ستيلار. إذا لم تكن مهتمًا بالتفاصيل ، فإليك نظرة عامة على العملية.

1. عقد عقد جولات من التصويت الاتحادي على "المرشحين". جولة التصويت الفيدرالي تعني:
   
   • تصوت العقدة لأي عبارة ، على سبيل المثال ، "أقترح قيمة V" ؛
     
   • تستمع العقدة إلى أصوات الأعياد حتى تجد واحدة يمكنها "استقبال" ؛
     
   • تبحث العقدة عن "النصاب القانوني" لهذا البيان. النصاب "يؤكد" المرشح.
2. بمجرد أن تتمكن العقدة من تأكيد مرشح واحد أو أكثر ، تحاول "إعداد" "اقتراع" من خلال عدة جولات من الاقتراع الفيدرالي.
   
3. بمجرد أن تتمكن العقدة من التحقق من جاهزية الاقتراع ، يحاول إطعامها بجولات أكثر من الاقتراع الموحد.
   
4. بمجرد أن يتمكن موقع ما من تأكيد التزام نشرة إخبارية ، يمكنه "إضفاء الطابع الخارجي" على قيمة هذه الرسالة الإخبارية ، واستخدامها كنتيجة للتوافق.

تتضمن هذه الخطوات عدة جولات من التصويت الموحد ، والتي تشكل معًا جولة واحدة من SCP. سوف ندرس بمزيد من التفصيل ما يحدث في كل خطوة.

التصويت الموحد

التصويت الموحد هو عملية تحديد ما إذا كان يمكن لشبكة ما الاتفاق على اقتراح. في جولة التصويت ، يجب أن تحدد كل عقدة واحدة من العديد من القيم المحتملة المحتملة. لا يستطيع القيام بذلك حتى يتأكد من أن العقد الأخرى على الشبكة لن تختار نتيجة مختلفة. للتأكد من ذلك ، تتبادل العقد سلسلة من الرسائل ذهابًا وإيابًا بحيث يؤكد الجميع أن نصاب العقد يتخذ القرار نفسه. يوضح الجزء المتبقي من هذا القسم المصطلحات في هذه الجملة وكيفية سير الإجراء بأكمله.

النصاب القانوني وشرائح النصاب

لنبدأ بتحديد النصاب القانوني. كما ناقشنا أعلاه ، في شبكة لا مركزية ذات عضوية ديناميكية ، من المستحيل معرفة عدد العقد مقدمًا ، وبالتالي ، ما هو المطلوب بالنسبة لمعظم الأشخاص. يحل التصويت الموحد هذه المشكلة عن طريق تقديم فكرة جديدة لشريحة النصاب القانوني: مجموعة صغيرة من العقد النظيرة التي تثق بها العقدة لنقل معلومات حالة التصويت في بقية الشبكة. تعرّف كل عقدة شريحة النصاب الخاصة بها (والتي تصبح عضوًا في الواقع).

يبدأ النصاب القانوني بقصاب النصاب. لكل عقدة ، يتم إضافة العقد من شريحة لها. ثم ، يتم إضافة أعضاء القطاعة من هذه العقد ، وهلم جرا. أثناء المتابعة ، تظهر المزيد من العقد التي لا يمكنك إضافتها ، لأنها مضمنة بالفعل في الشريحة. عندما لا توجد نقاط جديدة لإضافتها ، تتوقف العملية: لقد شكلنا النصاب القانوني من خلال "الإغلاق متعدية" عن طريق قطع النصاب القانوني للعقدة الأولية.


للعثور على النصاب القانوني من هذه العقدة ...


... إضافة أعضاء إلى شريحة ...


... ثم أضف أعضاء القطاعة إلى هذه العقد.


تابع حتى لا توجد نقاط لإضافتها.




لا العقد لإضافة اليسار. هذا هو النصاب القانوني.

في الواقع ، يمكن أن تذهب كل عقدة إلى أكثر من شريحة واحدة. لتشكيل النصاب القانوني ، حدد واحدة فقط من الشرائح وإضافة أعضاء ؛ ثم حدد أي شريحة لكل عضو وأضف أعضاء إلى تلك الشريحة وما إلى ذلك. هذا يعني أن كل عقدة هي عضو في العديد من النصوص القانونية الممكنة.


حدد شريحة نصاب واحدة فقط في كل خطوة.






النصاب القانوني ممكن واحد. أو بديل ...


... حدد شرائح أخرى ...




... (عند الإمكان) ...


... يخلق النصاب القانوني الآخر.

كيف تعرف العقدة الشرائح الموجودة في العقد الأخرى؟ بنفس الطريقة مثل المعلومات الأخرى حول العقد الأخرى: من عمليات الإرسال التي تبثها كل عقدة إلى الشبكة عندما تتغير حالة التصويت الخاصة بها. يتضمن كل بث معلومات حول شرائح العقدة المرسلة. لا تحدد الوثيقة الفنية لـ SCP آلية اتصال. تستخدم التطبيقات عادة بروتوكول gossip لضمان رسائل البث عبر الشبكة.

تذكر أنه في نظام الاتفاقات البيزنطية غير الفيدرالية ، يتم تعريف النصاب القانوني على أنه غالبية العقد. تم تطوير نظام الاتفاقات البيزنطية من وجهة نظر السؤال: كم عدد العقد غير شريفة التي يمكن للنظام تحملها؟ في نظام من العقد N مصمم للبقاء مع فشل f (الحيل) ، يجب أن تكون العقدة قادرة على إحراز تقدم من خلال تلقي استجابة من أقرانها N ، نظرًا لأن f منهم قد لا يعمل. ولكن بعد تلقي استجابة من نظرائهم من N - f ، يمكننا أن نفترض أن جميع أقرانهم (الذين لم تتلقَّ العقدة منهم استجابة) صادقون بالفعل. وبالتالي ، فإن f من أقرانهم من N - f (والتي يتم تلقي استجابة منها) ضارون. ولكي تتوصل العقد إلى نفس الإجماع ، يجب أن تكون غالبية العقد المتبقية صادقة ، أي أننا بحاجة إلى أن تكون N - f أكبر من 2f أو N> 3f. لذلك عادةً ما يكون للنظام المصمم للبقاء على قيد الحياة f مجموع N = 3f + 1 عقد وحجم النصاب القانوني 2f + 1. بمجرد أن يتجاوز الاقتراح حد النصاب القانوني ، فإن بقية الشبكة مقتنعة بأن أي مقترحات منافسة ستفشل. لذلك تتقارب الشبكة مع النتيجة.

لكن في نظام الاتفاقات البيزنطية الفيدرالية ، لا يمكن أن تكون هناك أغلبية فقط (لأنه لا أحد يعرف الحجم الكلي للشبكة) ، ولكن مفهوم الأغلبية لا فائدة منه عمومًا! إذا كانت العضوية في النظام مفتوحة ، فبإمكان أي شخص الحصول على الأغلبية بمجرد إجراء ما يسمى هجوم Sibyl: من خلال الانضمام المتكرر للشبكة عبر عدة عقد. فلماذا يمكن أن يسمى الإغلاق متعدية لشريحة النصاب القانوني ، وكيف يمكن قمع العروض المتنافسة؟

من الناحية الفنية ، لا مفر! تخيل شبكة من ست عقد ، حيث يتم عزل ثلاثين في شرائح من النصاب القانوني لكل منهما. يمكن للمجموعة الفرعية الأولى اتخاذ قرار بشأن المجموعة الثانية التي لن تسمعها أبدًا ، والعكس صحيح. لا توجد وسيلة لهذه الشبكة للوصول إلى إجماع (باستثناء الصدفة).

لذلك ، يتطلب SCP أن يكون للشبكة خاصية تسمى النصاب القانوني للعبور الموحد (ولتطبيق نظريات المقال المهمة). على شبكة مع هذه الخاصية ، يتداخل أي نصين يمكن تكوينهما دائمًا في عقدة واحدة على الأقل. لتحديد المزاج السائد للشبكة جيدة مثل وجود الغالبية. حدسي ، هذا يعني أنه إذا وافق النصاب القانوني على العبارة X ، فلن يتمكن النصاب القانوني الآخر من الاتفاق على شيء آخر ، لأنه سيشمل بالضرورة بعض العقدة من النصاب القانوني الأول الذي صوت بالفعل لصالح X.


إذا كانت الشبكة لديها تقاطع النصاب ...


... ثم أي نصابين يمكنك بناء ...


... سوف تتقاطع دائما.





(بالطبع ، قد تتحول العقد المتداخلة إلى كذبة بيزنطية أو سيئة في نواح أخرى. في هذه الحالة ، لا يساعد النصاب المتقاطع الشبكة على الاتفاق على الإطلاق. ولهذا السبب ، تستند العديد من النتائج في الورقة الفنية لـ SCP إلى افتراضات صريحة ، مثل ما تبقى على الشبكة تقاطع النصاب القانوني حتى بعد إزالة العقد السيئة . للبساطة ، نترك هذه الافتراضات ضمنية في بقية المقالة).

قد يبدو من غير المعقول توقع أنه في شبكة من العقد المستقلة يكون التقاطع الموثوق للنصوص ممكنًا. ولكن هناك سببان وراء ذلك.

السبب الأول هو وجود الإنترنت نفسها. الإنترنت هو مثال مثالي على شبكة من العقد المستقلة مع تقاطع النصاب القانوني. تتصل معظم المواقع على الإنترنت ببعض المواقع المحلية الأخرى فقط ، لكن هذه المجموعات الصغيرة تتداخل بما يكفي لجعل كل موقع يمكن الوصول إليه من كل موقع آخر على طريق معين.

السبب الثاني خاص بشبكة الدفع Stellar (الاستخدام الأكثر شيوعًا لـ SCP). كل أصل في شبكة Stellar لديه مصدر ، وتوصيات Stellar تتطلب من كل مصدر تعيين عقدة واحدة أو أكثر في الشبكة لمعالجة طلبات السداد. من مصلحتك تضمين هذه العقد بشكل مباشر أو غير مباشر في شرائح النصاب القانوني لكل أصل يهمك. ثم تتداخل النصاب القانوني لجميع العقد المهتمة بهذا الأصل على الأقل في عقد السداد هذه. ستشمل العقد المهتمة بالعديد من الأصول في شرائح النصاب الخاصة بها جميع عقد السداد للمصدرين المعنيين ، وستعمل جاهدة على الجمع بين جميع الأصول معًا. بالإضافة إلى ذلك ، أي أصول غير مرتبطة بهذه الطريقة مع الآخرين على الشبكة ولا يجب أن تكون متصلاً - الغرض منها هو عدم وجود عبور نصاب قانوني لهذه الشبكة (على سبيل المثال ، تريد البنوك من منطقة الدولار في بعض الأحيان التداول مع البنوك من منطقة اليورو والبنوك من منطقة البيزو ، لذلك هم على نفس الشبكة ، ولكن لا أحد منهم يهتم بشبكة منفصلة من الأطفال الذين يبيعون بطاقات البيسبول).

بطبيعة الحال ، فإن انتظار تقاطع النصاب القانوني ليس ضمانًا . تدين أنظمة الاتفاق البيزنطي الأخرى بالكثير من تعقيدها لضمان النصاب القانوني. يتمثل أحد ابتكارات SCP المهمة في أنه يزيل مسؤولية إنشاء النصاب القانوني من خوارزمية الإجماع نفسها ويصله إلى مستوى التطبيق. وبالتالي ، على الرغم من أن التصويت الفيدرالي عام إلى حد ما للتصويت على أي قضايا ، إلا أن موثوقيته تعتمد بشكل أساسي على المعنى الأوسع لهذه القيم. قد لا تكون بعض الاستخدامات الافتراضية ملائمة لبناء شبكات متصلة جيدًا مثلها مثل غيرها.

التصويت والقبول والتأكيد

في جولة التصويت الموحد ، تبدأ العقدة اختياريًا التصويت لبعض قيمة V. وهذا يعني أن الرسالة يتم إرسالها إلى الشبكة: "أنا العقدة N ، وشرائح النصاب القانوني هي Q ، وأنا أصوت لصالح V". عندما تصوت العقدة بهذه الطريقة ، يعد بأنه لم يصوت ضد V ولن يصوت أبدًا.

في عمليات البث من العقد من نظير إلى نظير ، ترى كل عقدة كيفية تصويت الآخرين. بمجرد أن تجمع العقدة عددًا كافيًا من هذه الرسائل ، يمكنها تتبع شرائح النصاب ومحاولة البحث عن النصاب. إذا رأى نصابًا من الأقران الذين يصوتون أيضًا لصالح V ، فيمكنه المتابعة لقبول V وبث هذه الرسالة الجديدة إلى الشبكة: "أنا العقدة N ، وشرائحي هي النصاب القانوني Q ، وأقبل V". يوفر القبول ضمانًا أقوى من التصويت البسيط. عندما تصوت العقدة لصالح V ، لا يمكنها أبدًا التصويت لصالح خيارات أخرى. لكن إذا قبلت العقدة V ، فلن تقبل أي عقدة على الويب خيارًا آخر (تثبت نظرية 8 في الورقة البيضاء التقنية SCP).

بالطبع ، من المحتمل جدًا ألا يكون هناك نصاب فوري للعقد يتفق مع V. قد تصوت العقد الأخرى لقيم أخرى. ولكن بالنسبة للموقع ، هناك طريقة أخرى للانتقال من التصويت البسيط إلى القبول. يمكن أن يأخذ N قيمة مختلفة من W ، حتى لو لم يصوت لصالحها ، وحتى إذا لم يشاهد النصاب القانوني لذلك. لاتخاذ قرار بتغيير صوتك ، يكفي رؤية مجموعة حظر من العقد قبلت W. مجموعة الحظر عبارة عن عقدة واحدة في كل شريحة من النصاب القانوني لـ N. كما يوحي الاسم ، يمكن أن تحظر أي قيمة أخرى. إذا كانت جميع العقد في مثل هذه المجموعة تأخذ W ، عندئذٍ (بواسطة Theorem 8) لن يكون من الممكن أبدًا تشكيل النصاب القانوني مع افتراض قيمة مختلفة ، وبالتالي يكون من الآمن أيضًا قبول W.


العقدة N مع ثلاث شرائح من النصاب القانوني.


BDF عبارة عن مجموعة حظر لـ N: تتضمن عقدة واحدة لكل شريحة من الشرائح N.


BE N, E N.

— . N, , N. — . N , , . , , SCP ( 11), , N .


.

عملية التصويت والقبول والتأكيد هي جولة كاملة من التصويت الموحد. يجمع بروتوكول توافق النجوم بين العديد من هذه الجولات لإنشاء نظام إجماع كامل.

بروتوكول توافق النجوم

— . «», ( ). «» , , .

, V, . « » — , - . , . , .

Stellar , , . ( SCP . , , , ). , , , SCP, .

, SCP , , - , , , . .

(nomination phase), « V», , V. — , .

SCP , , ( ) , (commit). , . , . — , , — .

.

في بداية مرحلة الترشيح ، يمكن لكل عقدة تحديد القيمة V تلقائيًا والتصويت للبيان "أنا ترشيح V". الهدف في هذه المرحلة هو تأكيد ترشيح قيمة معينة من خلال التصويت الفيدرالي.

, , . , «» . (echo) , V, , W, V, W. ( , . SCP . , «» , . , , , . , , ).

V, W — , . SCP .

V — V, — SCP — , «». SCP , « X», « X», . , . , .


ترشيح SCP باستخدام التصويت الموحد. يمكن أن يكون هناك العديد من القيم "B" التي يدفعها الأقران ويعكسها النظير.

ترشيح المرشحين قد يؤدي إلى العديد من المرشحين المؤكدين. لذلك ، يتطلب SCP طبقة التطبيق لتوفير بعض طريقة دمج المرشحين في مركب واحد . (composite). . , , . «» . ( : . , ). Stellar, , , , .

SCP ( 12), . : — ( SCP). , , , . , . , , , , .

. — . , (balloting).

— <counter,value>, counter — , 1, value — . , . , - - . , . <counter, value> , , <counter+1, value>.

(, : ), ( counter-value) . SCP , , :

• « B»
  
• « B»

من وجهة نظر هذه العقدة ، يتم الوصول إلى الإجماع عندما تعثر على النشرة B التي يمكنها تأكيدها (أي العثور على النصاب القانوني الذي يقبل) العبارة "أعلن الالتزام بالنشرة B". من الآن فصاعدًا ، يمكنك التصرف بأمان وفقًا للقيمة المحددة في B - على سبيل المثال ، ضع هذا الترتيب للغداء. وهذا ما يسمى القيمة الخارجية . بمجرد تأكيد قبول الاقتراع ، يمكن أن تتأكد العقدة من أن أي عقدة أخرى قد خرجت بنفس القيمة أو ستلتزم بها بالتأكيد في المستقبل.

على الرغم من أن العديد من بطاقات الاقتراع الموحدة من الناحية النظرية تُعقد على طلبات الحصول على العديد من بطاقات الاقتراع المختلفة ، إلا أنها لا تتبادل أكبر عدد من الرسائل لأن كل رسالة تحتوي على عدد من بطاقات الاقتراع. وبالتالي ، فإن هناك رسالة واحدة تعزز حالة العديد من الأصوات الفدرالية في آن واحد ، على سبيل المثال: "أقبل لجان الاقتراع في النطاق من <min ، V> إلى <max ، V>".

ماذا تعني المصطلحان "معد" و "التزام"؟

تصوت العقدة لإجراء اقتراع عندما تقتنع بأن العقد الأخرى لن تلتزم بأصوات ذات قيم مختلفة. إقناع هذا هو الغرض من إعداد البيان. التصويت الذي يقول "أنا مستعد لنشر نشرة ب" يعد بوعد بعدم نشر نشرة أقل من B ، أي باستخدام عداد أقل (تتطلب SCP أن يكون للقيم في النشرات ترتيب معين. النشرة <N1 ، V1> أقل من <N2 ، V2> إذا N1 <N2 ، وأيضًا إذا كانت N1 = N2 و V1 <V2). يتم "إحباط" هذه الأصوات الأصغر خلال التصويت التحضيري ، في حين تعتبر B "معدة".

لماذا تعني عبارة "أنا مستعد للالتزام بالنشرة" ب "لا أعد أبداً بالالتزام بأصوات أقل من B"؟ لأن SCP يعرف إحباط بأنه عكس الالتزام. يعني التصويت على إعداد الاقتراع أيضًا التصويت على إلغاء بعض بطاقات الاقتراع الأخرى ، وكما ناقشنا سابقًا ، فإن التصويت لشيء واحد هو وعد بعدم التصويت ضده أبدًا.

قبل بث الالتزام ، يجب على الموقع أولاً العثور على النشرة ، والتي يمكن تأكيدها على النحو الذي تم إعداده. بعبارة أخرى ، إنه يحمل تصويتًا موحدًا على "أنا مستعد للالتزام بالنشرة" ب "، ربما في العديد من بطاقات الاقتراع المختلفة ، حتى يجد صوتًا يقبل النصاب القانوني.

من أين تأتي بطاقات الاقتراع للتصويت؟ أولاً ، تبث العقدة الاستعدادات للتصويت لـ <1 ، C> ، حيث C هو المرشح المركب المنتج في مرحلة الترشيح. ومع ذلك ، حتى بعد بدء الاستعدادات للتصويت ، قد يؤدي الترشيح إلى ظهور مرشحين إضافيين سيصبحون بطاقات اقتراع جديدة. وفي الوقت نفسه ، قد يكون لدى أقرانهم مرشحين مختلفين ، ويمكنهم تشكيل مجموعة حظر تقبل "أنا مستعد لارتكاب نشرة B2" ، والتي ستقنع العقدة بقبولها أيضًا. أخيرًا ، هناك آلية مهلة تُنشئ جولات جديدة من التصويت الموحد على أوراق اقتراع جديدة ذات عدادات أعلى إذا كانت بطاقات الاقتراع الحالية عالقة.

بمجرد العثور على العقدة Bulletin B ، والتي يمكن تأكيدها عند الإعداد ، تبث رسالة جديدة ، "Bulletin B Commit". يخبر هذا التصويت أقرانه بأن العقدة لن تتنازل مطلقًا عن B. في الواقع ، إذا كانت B عبارة عن اقتراع <N ، C> ، فإن كلمة "Commit Bulletin <N، C>" تعني موافقة غير مشروطة للتصويت من أجل استعداد كل اقتراع من <N ، C> إلى <∞، s>. تساعد هذه القيمة الإضافية العقد الأخرى على اللحاق بالتزام ، إذا كانت لا تزال في المراحل الأولى من البروتوكول.

في هذه المرحلة ، يجدر التأكيد مرة أخرى على أن هذه البروتوكولات غير متزامنة. لمجرد أن عقدة واحدة ترسل أصواتًا لالتزام لا يعني أن أقرانها يقومون بذلك أيضًا. ما زال بإمكان البعض منهم التصويت على الطلبات استعدادًا للتصويت ، بينما ربما يكون البعض الآخر قد أخرج المعنى. يشرح SCP كيف يجب على العقدة معالجة كل نوع من رسائل النظير بغض النظر عن مرحلته.

إذا تعذر قبول أو تأكيد الرسالة "أعلن الالتزام <N ، C>" ، أي احتمال قبول أو تأكيد الرسالة <N + 1 ، C> أو <N + 2 ، C> - أو ، على أي حال ، أي نشرة بقيمة C ، وليس أي قيمة أخرى ، لأن العقدة وعدت بالفعل بعدم إلغاء <N ، C>. بحلول الوقت الذي تبث فيه العقدة الأصوات الخاصة بالالتزام ، ستكون C أو لا شيء ، وفقًا لمدى توافق الآراء. ومع ذلك ، هذا لا يكفي للعقدة الخارجية. بعض الأعياد البيزنطية (أقل من النصاب القانوني ، استنادا إلى افتراضاتنا حول الأمن) قد تقع على العقدة. إن اعتماد ثم تأكيد اقتراع معين (أو مجموعة من بطاقات الاقتراع) هو ما يمنح العقدة الثقة لتتمكن أخيرًا من الخروج الخارجي.


SCP يعمل من خلال التصويت الموحد. غير معروض: في أي وقت قد يعمل جهاز ضبط الوقت ، مما يؤدي إلى زيادة العداد في الاقتراع (وربما إنتاج مركب جديد من مرشحين إضافيين).

وهذا كل شيء! بمجرد أن تتوصل الشبكة إلى إجماع ، تصبح جاهزة للقيام بذلك مرارًا وتكرارًا. على شبكة الفوترة Stellar ، يحدث هذا كل 5 ثوانٍ تقريبًا: وهو إنجاز يتطلب الأمان والقدرة على البقاء ، ويضمنهما SCP.

يمكن لـ SCP تحقيق ذلك من خلال الاعتماد على عدة جولات من التصويت الموحد. تم إجراء التصويت الموحد بفضل مفهوم شرائح النصاب: مجموعات من العقد النظيرة التي قررت كل عقدة الوثوق بها كجزء من النصاب القانوني (الذاتي). يعني هذا التكوين أنه يمكنك الوصول إلى إجماع حتى على شبكة ذات عضوية مفتوحة وخداع بيزنطي.

مزيد من القراءة

• يمكن الاطلاع على المستند التقني SCP الأصلي هنا ، وهنا هو مشروع المواصفات لتنفيذه.
  
• المؤلف الأصلي لبروتوكول SCP ، David Mazier ، يبسط (ولكن لا يزال تقنيًا) يشرح ذلك هنا .
  
• ربما فوجئت بعدم العثور على المصطلحات "التعدين" أو "إثبات العمل" في هذه المقالة. لا يستخدم SCP هذه الطرق ، لكن بعض خوارزميات الإجماع الأخرى تستخدم. Zane Witherspoon كتب مراجعة يمكن الوصول إليها من خوارزميات الإجماع .
  
• وصف تفصيلي لشبكة بسيطة تحقق التوافق في جولة واحدة كاملة من SCP.
  
• بالنسبة للقراء المهتمين بتطبيقات SCP: راجع رمز C ++ المستخدم من قبل شبكة الدفع Stellar ، أو رمز Go كتبته لفهم SCP بشكل أفضل.