НОУ ІНТУІТ, Лекція, Розподілені завдання та алгоритми

З системою S пов'язана мета G, заради якої система функціонує. Ця мета ставиться системою (якщо система – активна), чи поставлена ззовні. Для досягнення мети в системі має вирішуватись завдання – деяка математична формалізація мети з чітко визначеним набором вихідних даних та необхідних результатів.

Розв'язання завдання передбачається одержувати з допомогою алгоритму, тобто. приписи із зазначенням виконавця (виконавців) та послідовності елементарних кроків, які мають бути зроблені виконавцями.

Розподілена система породжує розподілене завдання, оскільки вихідні дані завдання виникають у різних точках простору. Також у різних точках потрібні ті чи інші результати розв'язання задачі. Часто завдання можна розбити в сукупність підзадач, деякі з них можуть бути зосередженими: всі вихідні дані виникають в одній точці простору, і там же потрібні результати рішення підзавдання.

Розподілена задача вирішується розподіленим алгоритмом, що збирає вихідні дані з різних точок і посилає результати розрахунків у різні точки. Додатковим чинником розподіленості алгоритму може бути кілька виконавців, що у різних точках простору (розподілений виконавець ).

Відомо, що алгоритм оперує крім вихідних даних, ще й проміжними даними, а великих системах працює з базами даних. Для розподіленого алгоритму закономірно постає питання: як буде організовано ці дані – як зосередженої чи розподіленої бази даних ?

Один із видів розподілених алгоритмів – протоколи. Протокол характеризується тим, що є, як мінімум, дві сторони, розділені каналом зв'язку. На кожній із сторін виконуєтьсялокальний (зосереджений) алгоритм Ak. Локальний алгоритм A1 виконується до деякого моменту часу, коли для продовження роботи йому потрібні дані іншого локального алгоритму A2 . Він посилає через лінію зв'язку запит на дані локальному алгоритму A2. Алгоритм A2 відповідає, надсилаючи повідомлення по лінії зв'язку. Після цього локальний алгоритм A1 продовжує свою роботу.

Протоколи зазвичай відіграють технічну роль і служать для встановлення режимів прийому/передачі даних між віддаленими об'єктами. У обчислювальному відношенні локальні алгоритми – частини протоколу – не є складними.

Особливий вид розподілених алгоритмів – криптографічні протоколи. Вони призначені для доказу однією або обома сторонами, що саме ті, за кого себе видають, для обміну конфіденційною інформацією та інших подібних цілей.

Розглянемо один із найпростіших криптографічних протоколів – розподілених алгоритмів.

У різних точках простору знаходяться два об'єкти, O1 і O2, кожен з яких вирішує свою частину (P1 або P2) загального завдання P. Разом про те, крім прагнення розв'язати загальне завдання, об'єкти мають свої приватні завдання, Q1 і Q2 . Таким чином, об'єкт O1 вирішує одночасно задачі P1 і Q1, а об'єкт O2 - задачі P2 і Q2. І, якщо задачі P1 та P2 сумісні та взаємно доповнюють один одного, то задачі Q1 та Q2 – суперечать один одному.

Отже, об'єкти O1 і O2 співпрацюють, але водночас і конкурують. А можна сказати і те, що об'єкти конкурують, але змушені співпрацювати. Дивлячись як розставити акценти, яке із завдань, Pi або Qi, важливіше для об'єкта Oi.

Описана ситуація трапляється дуже часто. Університети зацікавлені у вирішенні завдання вдосконалення підготовки спеціалістів і в цьому вониспівпрацюють. Водночас щороку виші конкурують через здібних абітурієнтів. Наукові організації часто проводять спільні дослідження з кінця їх інтересів (з кінця наук). Але ж вони конкурують при розподілі фінансів. Два різних підрозділи фірми працюють задля досягнення загальних цілей фірми, але з них хоче отримати у межах фірми більшого розвитку, ніж інший підрозділ. Загалом, друзі-суперники. Часткова конкуренція.

У нашій задачі об'єкти O1 і O2 повинні дійти загального компромісного рішення на користь розв'язання задачі P . Припустимо, що є два рівноцінні (з точки зору задачі P) рішення. Одне також влаштовує об'єкт O1 , інше – влаштовує об'єкт O2 . Тоді об'єкти O1 та O2 вирішують кинути жереб. Це можна зробити: написати кожне рішення на своєму папірці, згорнути папірці в трубочку, прокрутити в лототроні і один з папірців витягнути. Це і буде компромісне рішення.

Складність у тому, що об'єкти O1 і O2 перебувають у великій відстані друг від друга, і можуть провести процедуру з лототроном. Процедура з лототрон виконується в одному місці, вона можлива для зосередженої системи. Наша система – розподілена.

Процедуру з лототроном міг би виконати об'єкт O1 та повідомити результат об'єкту O2. Однак об'єкт O2 не цілком довіряє об'єкту O1. Навіть телевізійна трансляція виконання процедури не є переконливим доказом – це може бути майстерно змонтований запис.

Вихід полягає у наступному. Позначимо одне з рішень числом 0, інше – числом 1. Кожен із об'єктів незалежно від іншого має назвати якесь ціле число ni в межах, наприклад, від 0 до 99. Потім об'єкти обмінюються числами ni та обчислюють результат n1 + n2 (mod 2 ). І це буде рішення, тобто.число 0 чи 1.

Абсолютно одночасно переслати один одному числа ni об'єкти не можуть. Хтось надішле своє число першим і опиниться в невиграшному становищі. Наприклад, O1 переслав своє число n1 об'єкту O2 зацікавленому в тому, щоб виграло рішення "1". Тоді O2 знаючи n1 вирішує рівняння n1 + n2 (mod 2) = 1 щодо змінної n2 і посилає O1 знайдене значення n2 . Рішення рівняння практично не вимагає часу: отримавши від O1 парне число, O2 має відповісти непарним, і навпаки.

Ця несправедливість має бути усунена. При цьому ясно, що все одно якась із сторін обміну повідомленнями першою надішле своє число. Необхідно зробити так, щоб у другої сторони забракло часу на "підбір відповіді".

Об'єкти O1 та O2 можуть домовитися, що вся процедура "кидання жереба" на відстані має завершитися за кілька хвилин. Якщо обидва об'єкти знають, що підбір відповіді вимагає кількох годин роботи суперЕОМ, то вони можуть бути спокійні за те, що рішення не "підлаштоване" іншою стороною.

Для забезпечення таких часових параметрів у обчисленнях має використовуватися функція f(x) , значення якої y = f(x) за відомого аргументу x обчислити можна відносно швидко. Але вирішити рівняння f(x) = y , тобто. знайти невідоме x при відомому значенні y швидко не можна. Більш того, бажано, щоб не було відомо жодних математичних методів для вирішення цього рівняння, крім повного перебору або подібного до нього за складністю.

Звичайно, область визначення функції f(x) повинна бути при цьому дуже великою, щоб унеможливити повний перебір. Область із двох елементів, 0 і 1, мала, область від 0 до 99 теж недостатня. Цілі числа, з якими доводиться оперувати, повинні мати у десятковійзаписи не менше 150-200 цифр або не менше 512 біт у двійковому записі. Такі числа називають "довгими".

Нехай f(x) і h(z, v, w) – дві таких функції, що важко обертаються. У функції h(z, v, w) перші два аргументи – довгі числа, а третій – бітовий. Функції f і h відомі об'єктам O1 і O2 і вони володіють алгоритмами швидкого обчислення значень цих функцій при заданих значеннях аргументів, але не вміють швидко звертати ці функції, тобто. розв'язувати рівняння.

Розподілений алгоритм кидання жереба складається з наступних кроків.

Об'єкт O2 вибирає випадково число x з великого інтервалу [0, q – 1] . Обчислює y = f(x).
Об'єкт O2 пересилає число y об'єкту O1. Об'єкт O1 зможе відновити число x .
Об'єкт O1 вибирає випадковим чином число z великого інтервалу [0, q - 1] . Об'єкт O1 вибирає випадковий біт w. Ці дії можуть виконуватись одночасно з п.1.
Об'єкт O1 обчислює s = h (z, y, w). Число z тут необхідно для "маскування" біта w, а число y - для "перевірки" об'єктом O2 правильності дій об'єкта O1.
Об'єкт O1 пересилає число s об'єкту O2. Біт w відправляється об'єкту O2, але він "захований" у числі s. Об'єкт O2 зможе відновити цей біт. Об'єкт O2 зможе відновити і число z .
Об'єкт O2 вибирає випадковий біт c.
Об'єкт O2 відправляє біт з об'єкту O1. Відкрите пересилання.
Об'єкт O1 пересилає число z і біт w об'єкту O2. Відкрите пересилання. Об'єкт O1 може визначити результат кидання жереба: c + w (mod 2) .
Об'єкт O2 обчислює t = h (z, y, w). Тут z і w щойно отримані від O1 а y було обчислено в п.1.
Об'єкт O2 порівнює t і s раніше отримане від об'єкта O1.
Якщо t = s, то об'єкт O2 обчислює результат киданняжереба: c + w (mod 2).

Функції f та h можуть бути різними. Зокрема, використовуються функції:

f(x) = g x (mod p) і h(z, v, w) = v w g z (mod p).

Тут "секретні" значення x, w, z знаходяться в показниках ступенів, і для того, щоб знайти їх, потрібно вирішити задачу дискретного логарифмування, для якої ефективний алгоритм, суттєво кращий за повний перебір, невідомий.

Константи p, q, g повинні бути відомі тому та іншому об'єктам. Число p – довге просте число. Число q - також довге просте число, що є дільником числа p - 1. Число g не дорівнює 1, задовольняє умові g q = 1 (mod p) .

Розподілені алгоритми, що вирішують зосереджені завдання.

Один із напрямів у розробці розподілених алгоритмів – високопродуктивні обчислення. Розподілена комп'ютерна система у разі використовується як потужний обчислювач, вирішальний одне завдання. Відомим прикладом є завдання "зламування" шифру, створеного алгоритмом шифрування DES. Дешифрування тексту не становить труднощів, якщо відомий ключ шифрування. Якщо ключ не відомий, дешифрування можна спробувати виконати шляхом повного перебору. Але метод повного перебору вимагає дуже багато часу навіть найшвидших однопроцессорных ЕОМ.

Розв'язання задачі можна прискорити, використовуючи багатопроцесорну ЕОМ. І тут обчислення розпаралельуються, тобто. всі процесори одночасно, виконуючи однакові чи різні команди, беруть участь у розв'язанні задачі. Як саме відбувається розпаралелювання - залежить від архітектури багатопроцесорної ЕОМ. За наявності у її складі n процесорів в ідеальній ситуації прискорення обчислень може досягати величини, близької n разів. Реально, алгоритми не повністю розпаралелюються, частинапроцесорів може простоювати в окремі періоди часу, і продуктивність збільшується менш ніж у n разів.

Сучасні багатопроцесорні машини мають десятки та сотні процесорів, окремі – тисячі процесорів. Але такі унікальні машини дуже дорогі, встановлені у спеціальних суперкомп'ютерних центрах або військових організаціях і не завжди доступні рядовим користувачам.

Альтернативою є використання окремих комп'ютерів, з'єднаних глобальними мережами зв'язку, що належать приватним особам та різним організаціям. Комп'ютери можуть мати відносно невисоку продуктивність, але використання в мережі відразу кількох десятків або сотень тисяч комп'ютерів для вирішення одного завдання створює ефект того ж суперкомп'ютера, але, можливо, ще потужнішого.

Саме така розподілена комп'ютерна система використовувалася для цього завдання дешифрування. Це не була "жорстка" система - комп'ютери використовувалися на добровільній основі, у будь-який момент часу будь-який комп'ютер міг вийти із системи. Але так само і нові комп'ютери могли приєднуватися до працюючих.

Ідея та відповідна технологія використання глобальної мережі комп'ютерів для вирішення складного завдання одержала назву Grid. Якщо Web забезпечує доступ до глобальних інформаційних ресурсів, то Grid має забезпечити доступ до глобальних обчислювальних ресурсів. Основні проекти використання Grid в даний час пов'язані з обробкою великої кількості (терабайти, пентабайти) експериментальних даних у фізиці елементарних частинок, спостережень в астрономії, розшифровкою геному людини в біології.