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

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

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

أنظمة الاتفاق

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

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

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

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

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

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

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

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

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

للصبر

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

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

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

التصويت الفيدرالي

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

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

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

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

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

...إضافة أعضاء من شريحتها...

...ثم نضيف أعضاء شريحة من هذه العقد.

نستمر حتى لا يتبقى أي عقد لإضافتها.

لا توجد عقد متبقية لإضافتها. هذا هو النصاب القانوني.

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

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

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

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

…(عندما يكون ذلك ممكنا)…

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

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

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

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

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

لذلك، يتطلب 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، فلن يكون من الممكن أبدًا (بواسطة النظرية 8) تكوين نصاب يأخذ قيمة مختلفة، وبالتالي فمن الآمن أيضًا أن يقبل N W.

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

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

BE هي أيضًا مجموعة حظر لـ N لأن E تظهر في شريحتين من N.

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

التصويت الفيدرالي.

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

بروتوكول الإجماع النجمي

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

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

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

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

تجرى الجولات الأولى من التصويت الفيدرالي في مرحلة الترشيح (مرحلة الترشيح)، على مجموعة من العبارات مثل "أنا أرشح V"، ربما للعديد من القيم المختلفة لـ V. الغرض من الترشيح هو العثور على عبارة واحدة أو أكثر تمر عبر القبول والتأكيد.

بعد العثور على مرشحين يمكن التحقق منهم، ينتقل SCP إلى مرحلة التصويت، حيث يكون الهدف هو العثور على مرشح معين бюллетень (أي حاوية للقيمة المقترحة) والنصاب القانوني الذي يمكن إعلانه ارتكب لذلك (الالتزام). إذا توافر النصاب القانوني للاقتراع، يتم قبول قيمته كإجماع. ولكن قبل أن تتمكن العقدة من التصويت على التزام الاقتراع، يجب عليها التأكيد أولاً إلغاء جميع بطاقات الاقتراع ذات قيمة عداد أقل. تتضمن هذه الخطوات - إلغاء بطاقات الاقتراع للعثور على بطاقة يمكن الالتزام بها - جولات متعددة من التصويت الفيدرالي على مطالبات اقتراع متعددة.

تصف الأقسام التالية الترشيح والتصويت بمزيد من التفصيل.

ترشيح

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

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

من الناحية النظرية، يكون الترشيح متوازيًا، فكل من V وW عبارة عن صوتين فيدراليين منفصلين، كل منهما قادر بشكل فردي على تحقيق القبول أو التأكيد. ومن الناحية العملية، تقوم رسائل بروتوكول SCP بتجميع هذه الأصوات الفردية معًا.

على الرغم من أن التصويت لصالح ترشيح V هو وعد بعدم التصويت مطلقًا ضد ترشيح V، إلا أنه على مستوى التقديم - في هذه الحالة SCP - يتم تحديد معنى كلمة "ضد". لا يرى SCP عبارة تتعارض مع تصويت "أنا أرشح X"، أي أنه لا توجد رسالة "أنا ضد ترشيح X"، لذلك يمكن للعقدة التصويت لترشيح أي قيم. لن تؤدي العديد من هذه الترشيحات إلى أي مكان، ولكن في النهاية ستكون العقدة قادرة على قبول أو تأكيد قيمة واحدة أو أكثر. بمجرد تأكيد المرشح، يصبح مُرَشَّح.

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

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

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

لكنه طبيعي. الترشيح هو مجرد تحضير. والشيء الرئيسي هو الحد من عدد المرشحين لتحقيق الإجماع، وهو ما يحدث في هذه العملية الاقتراع (الاقتراع).

جري

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

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

• "أنا مستعد لإجراء الاقتراع ب" و
• "أعلن الالتزام بالاقتراع ب"

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

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

ماذا تعني عبارة "مستعد" و"ملتزم"؟

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

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

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

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

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

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

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

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

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

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

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

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

المصدر: www.habr.com