4.3. Оптимальні схеми відновлення
Послідовності в R(n, p) іноді звані p−оптимальні послідовності.
Визначення 1. Множина R*(n) = R(n, n – 1) − сукупність послідовно оптимальних схемвідновлення.
Головна
мета цієї статті − описати множини для
усього n
і його навантаження послідовність SV.
Порівнянням з попередньою роботою в
цьому плані як описано спочатку у Секції
3, такий опис виснажив би це проблемне
формулювання. Нехай
.
Для усіх R
R(n),
це доводиться в [20] що MV
≤ L(n,
j,
R)
хоча j =
1,2,
…,
p.
Не відомо, якщо нижчий MV межі щільні. У цій статті ми розслідуємо напруженість з пов'язаного MV оптимальний послідовність навантаження SV . Ми подали алгоритм, з яким ми обчислюємо оптимальну межу SV. У багатьох зразках, коли ми маємо більший ряд пошкоджених комп'ютерів, SV не співпадають з MV.
5. Головні результати
У цій секції ми подали метод, для досягнення максимального навантаження в найгіршому випадку поведінки після p вимкнень.
5.1. Комп'ютерні ланцюги
Обчислення оптимальних послідовностей стає здійснимим наступним формулюванням задачі в ланцюгах і об'єднаннях ланцюгів. Щоб вивчати балансування навантаження, ми переключаємо перспективу до точки зору комп'ютера y, який отримує процеси від деякої кількості аварій комп'ютерів.
Ланцюг − послідовність xi, 1, xi, 2, …, xi, j списоку відновлення, яка закінчується в комп'ютері y, тобто y =xi, j. Це отже представляє шлях, що i−тий процес (процес i−того комп'ютера) бере, щоб закінчитися в комп'ютері y. Змінна j означає число збійних кроків до y. Якщо, ми говоримо, що цей процес i має відстань j до комп'ютера y. Починаючи з входу для кожного виправленого i в кожному регулярному списку відновлень, існує точно один процес з відстанню j, для усього . Ми, можливо, потім упорядковуємо ланцюги
збільшуючи відстань до y:
L1 = {y1,1}
L2 y2,1, y2, 2 = { }
Ln – 1 ={yn–1,1,yn–1,2,…,yn – 1, n – 1}
У цій секції усі схеми відновлення і ланцюги перераховуються в змісті модуля. Не може бути двох ланцюгів тієї ж довжини, відколи це мало б на увазі, що процеси були породжені в тому ж комп'ютері. Ми підсумовуємо: кожен ланцюг представляє шлях для процесу, який перенесений з комп'ютера y наступними комп'ютерними вимкненнями. Кожен вхід в ланцюги представляє комп'ютер, який вимкнений.
Регулярний список відновлень дає ланцюги:
{y–R1} (mod n)
{y–R2, y – (R2 – R1)} (mod n)
{ y–R3,y–(R3 – R1), y-(R3 – R2)} (mod n)
…
{y–Rn – 1,y–(Rn – 1 – R1), …,y –(Rn – 1 – Rn – 2)} (mod n)
Ми, можемо, альтернативно описати регулярну схему відновлення R = {0, R1, …, Rn – 1} різницями r= {r1, r2, …, rn – 1}. Ми визначаємо
r1 = R1 (mod n)
r2 = R2 – R1(mod n)
r3 = R3 – R2(mod n)
…
rn – 1 = Rn – 2 – Rn – 1(mod n)
і отже
R1 = r1(mod n)
R2 = r1 + r2(mod n)
…
Rn – 1 = r1+r2+…+rn – 1(mod n)
Близькі регулярні схеми відновлення потім дано:
0. {r1, r1 + r2, r1+r2+r3, …, r1+…+rn – 1} (mod n)
1. {r1 + 1, r1 + r2 + 1, …, r1+…+rn – 1+1} (mod n)
…
n-1 {r1 + n – 1, …, r1+…+rn – 1+n – 1} (mod n)
Ланцюги комп'ютерів, що закінчуються в y, є як зазначено нижче:
{y–r1} (mod n),
{y–(r1 + r2),y–r2} (mod n),
{y–(r1+r2+r3),y–(r2 + r3),y–r3} (mod n),
…
{y–(r1+…+rn – 1), …,y–(rn – 2 + rn – 1),y–rn – 1} (mod n),
Властивості, в яких ми зацікавлені, більші легко вивчився в наступній версії:
C1 = {r1} (mod n),
C2 = {r1 + r2, r2} (mod n),
C3 ={r1+r2+r3, r2 + r3, r3} (mod n),
…
Cn – 1 ={r1+…+rn – 1, …, rn – 2 + rn – 1, rn – 1} (mod n),