حساب احتمال فشل النظام في شبكة توزيع

Question

أنا أحاول بناء نموذج رياضي من توافر ملف في توزيع نظام الملفات.أنا سجلت في هذه المسألة في MathOverflow ولكن هذا قد يكون كذلك تصنف CS-السؤال حتى أعطيها فرصة هنا كذلك.

نظام يعمل مثل هذا:عقدة مخازن ملف (encoed باستخدام رموز محو) في ص*ب أجهزة التحكم عن بعد العقد ، حيث r هو تكرار عامل و b هو عدد صحيح ثابت.المحو ترميز الملفات الممتلكات التي يمكن استعادة الملف iff على الأقل ب البعيد العقد متوفرة و العودة جزء من الملف.

أبسط لهذا النهج هو أن نفترض أن جميع البعيد العقد مستقلة بعضها البعض ولها نفس توافر p.مع هذه الافتراضات توافر ملف يتبع توزيع ذي الحدين ، أي توزيع ذات الحدين http://bit.ly/dyJwwE

للأسف اثنين من هذه الافتراضات يمكن إدخال غير neligible الخطأ ، كما هو مبين من خلال هذه الورقة: http://deim.urv.cat/~lluis.pamies/uploads/الرئيسية/icpp09 ورقة.pdf.

طريقة واحدة للتغلب على افتراض أن كل عقد يكون نفس توافر لحساب احتمال كل تركيبة ممكنة من availaible/غير المتاحة عقدة واتخاذ مجموع كل هذه النتائج (الذي هو نوع من ما توحي في الورقة أعلاه, فقط أكثر رسميا من ما وصفتها).يمكنك أن ترى أن هذا النهج شجرة ثنائية مع عمق r*b و ترك كل واحد ممكن مزيج المتاحة/غير المتاحة العقد.الملف توافر هي نفس الشيء مثل probablity أن تصل في إجازة مع >=b المتاحة العقد.هذا النهج هو الأصح ولكن لديه الحسابية تكلفة Ordo http://bit.ly/cEZcAP.كما أنه لا يتعامل مع افتراض عقدة الاستقلال.

هل لديكم أي أفكار جيدة التقريب الذي يقدم أقل خطأ من توزيع ذي الحدين-aproximation ولكن مع أفضل الحسابية تكلفة من http://bit.ly/d52MM9 http://bit.ly/cEZcAP?

يمكنك أن تفترض أن توافر البيانات من كل عقدة مجموعة من المجموعات التي تتكون من (measurement-date, node measuring, node being measured, succes/failure-bit).مع هذه البيانات هل يمكن على سبيل المثال حساب الارتباط من توافر بين العقد و توافر الفرق.

Answer 1

كبيرة r و b يمكنك استخدام طريقة تسمى مونتي كارلو التكامل ، انظر على سبيل المثال مونت كارلو التكامل في ويكيبيديا (و/أو الفصل 3.1.2 من SICP) لحساب مجموع.الصغيرة r و b و مختلفة بشكل كبير عقدة الفشل الاحتمالات p[i] نفس طريقة متفوقة.التعريف الدقيق صغيرة و كبيرة سوف يعتمد على عدة عوامل و هي أفضل حاولت تجريبيا.

محددة في نموذج التعليمات البرمجية:هذا هو أساسي جدا نموذج التعليمات البرمجية (في بيثون) إظهار كيف أن مثل هذا الإجراء يمكن أن تعمل:

def montecarlo(p, rb, N):
    """Corresponds to the binomial coefficient formula."""
    import random
    succ = 0

    # Run N samples
    for i in xrange(N):
        # Generate a single test case
        alivenum = 0
        for j in xrange(rb):
            if random.random()<p: alivenum += 1
        # If the test case succeeds, increase succ
        if alivenum >= b: succ += 1
    # The final result is the number of successful cases/number of total cases
    # (I.e., a probability between 0 and 1)
    return float(succ)/N

وظيفة يتوافق مع الحدين اختبار حالة ويعمل N اختبارات التحقق إذا b العقد من r*b العقد على قيد الحياة مع احتمال فشل p.بعض التجارب سوف اقناع لكم أن كنت بحاجة القيم N في نطاق الآلاف من العينات قبل أن يمكنك الحصول على أي نتائج معقولة ، ولكن من حيث المبدأ على التعقيد O(N*r*b).دقة النتيجة المقاييس كما sqrt(N), أي زيادة دقة من قبل عامل من اثنين تحتاج إلى زيادة N من قبل عامل من أربعة.لمدة كبيرة بما فيه الكفاية r*b هذه الطريقة سوف تكون متفوقة بوضوح.

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

1) في حالة متميزة ولكن غير مترابطة p[i], التغييرات من رمز أعلاه هي الحد الأدنى:في وظيفة الرأس يمكنك تمرير صفيف بدلا من واحدة تطفو p و يمكنك استبدال الخط if random.random()<p: alivenum += 1 قبل

if random.random()<p[j]: alivenum += 1

2) في حالة مرتبطة p[i] كنت بحاجة إلى معلومات إضافية عن النظام.الوضع كنت أقصد في تعليقي أن تكون شبكة مثل هذا:

A--B--C
   |  |
   D  E
   |
   F--G--H
      |
      J

في هذه الحالة A قد تكون "عقدة الجذر" و فشل عقدة D يمكن أن يعني التلقائي فشل مع احتمال 100% من العقد F, G, H و J;في حين فشل عقدة F سوف تؤدي تلقائيا إلى أسفل G, H و J الخ.على الأقل كان هذا هو حال كنت أقصد في تعليقي (وهو تفسير معقول منذ تتحدث عن بنية شجرة الاحتمالات في السؤال الأصلي).في مثل هذه الحالة سوف تحتاج إلى تعديل التعليمات البرمجية التي p يشير إلى هيكل شجرة ، for j in ... تقطع شجرة تخطي فروع أقل من العقدة الحالية في أقرب وقت فشل الاختبار.مما أدى الاختبار هو ما إذا كان alivenum >= b كما كان من قبل, بالطبع.

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

4) الاعتماد الوقت هو غير تافهة ، ولكن من الممكن تعديل إذا كنت تعرف م.t.ب.f/r (يعني مرات بين الفشل/إصلاح) لأن هذا يمكن أن تعطيك احتمالات p إما في شجرة هيكل أو غير مترابطة الخطية p[i] عن طريق مبلغ من exponentials.سيكون لديك ثم قم بتشغيل MC-الإجراء في أوقات مختلفة مع نتائج المقابلة ل p.

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

Answer 2

على افتراض أن كل عقدة لها معدل توافر ثابت ومعروف ومستقل ، فإن مقاربة الفجوة والقهر تتبادر إلى الذهن.

قل لديك N العقد.

1. تقسيمها إلى مجموعتين من N/2 العقد.
2. لكل جانب ، احسب احتمال أن يكون أي عدد من العقد ([0,N/2]) إلى أسفل.
3. اضرب وتجمل هذه حسب الحاجة للعثور على احتمال أن أي رقم ([0,N]) من المجموعة الكاملة أسفل.

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

لا أعرف تعقيد هذا ولكن إذا كان علي تخمين ، فسأقول في أو أدناه O(n^2 log n)

---

يمكن توضيح ميكانيكا هذا في حالة الطرفية. قل أن لدينا 5 عقد مع أوقات ما يصل . يمكننا تقسيم هذا إلى شرائح A مع و B مع . يمكننا بعد ذلك معالجة هذه للعثور على أوقات "العقد n" لكل قطعة:

من أجل:

ل B:

يمكن العثور على النتائج النهائية لهذه المرحلة عن طريق ضرب كل من aمع كل من bوتلخيص بشكل مناسب.

v[0] = a[0]*b[0]
v[1] = a[1]*b[0] + a[0]*b[1]
v[2] = a[2]*b[0] + a[1]*b[1] + a[0]*b[2]
v[3] =             a[2]*b[1] + a[1]*b[2] + a[0]*b[3]
v[4] =                         a[2]*b[2] + a[1]*b[3]
v[5] =                                     a[2]*b[3]