خوارزمية انتخابات قادة لفرط فرط فرط فرط الحركة

Question

أنا عالق مع بعض المشكلات حيث يتعين علي تصميم خوارزمية الانتخابات القائدة للاختبار المفرط الموجهة. يجب أن يتم ذلك باستخدام البطولة مع عدد من الجولات تساوي البعد D من Hypercube. في كل مرحلة D ، مع 1 <= d <d ، يجب أن يتنافس اثنان من قادة المرشحين المجاورة لثلاثي الأبعاد المجاورة لتصبح الزعيم المرشح الوحيد لفرط الأبعاد (D+1)-وهو اتحاد Hypercubes لكل منهما.

Answer 1

لقد مر وقت طويل منذ أن درست الأنظمة الموزعة ، لكنني آمل أن يساعد هذا قليلاً :)

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

إذا فهمت بشكل جيد إرشادات الحل ، فيبدو أن الخوارزمية بسيطة: فإن العقدة لديها حالات د بالضبط. في كل حالة 1 <= d <= d ، يتواصل مع جارها على طول محور D. يتكون هذا الاتصال من إرسال معرف أفضل مرشح يدركه (عندما يكون D = 1 هو ببساطة معرفه الخاص) ، ومقارنته بالمعرف الذي تلقاه النظير. الآن تعرف العقدة أفضل معرف للترتيب الفرعي D (المحدد بواسطة المحاور 1،2 ... ، د) ينتمي إليه. وبهذه الطريقة ، في الخطوة D ، تكون جميع العقد على دراية بالأفضل العالمي ، وتتكمل الخوارزمية بتوافق الآراء.

على سبيل المثال ، افترض الطوبولوجيا التالية (D = 2) وقيم المعرف:

   (1)    (2)
    1-----2
    |     |
    |     |
    4-----3
   (4)    (3)

تشير المعرفات بين قوسين إلى أفضل المعرفات المعروفة من قبل كل عقدة حتى الآن.

يعمل التكرار الأول (D = 1) على طول المحور الأفقي ، وينتهي على النحو التالي:

   (2)    (2)
    1-----2
    |     |
    |     |
    4-----3
   (4)    (4)

يعمل التكرار الثاني (والأخير) (D = 2) على طول المحور العمودي ، وينتهي على النحو التالي:

   (4)    (4)
    1-----2
    |     |
    |     |
    4-----3
   (4)    (4)

تم اختيار الرقم 4 العقدة ، كما هو مطلوب (أعلى هوية).

تعقيد عدد الرسائل

لكل حافة في Hypercube لدينا رسالتين بالضبط (واحدة في كل اتجاه). نظرًا لأن صيغة عدد الحواف في فرط البعد D هي e = d*2^(d-1) ، لدينا بالضبط m = d*2^d. من أجل حساب التعقيد كدالة لـ N (عدد العقد) ، تذكر أن n = 2^d ، لذلك m = n*log n.