Алгоритм Марзулло

Алгоритм Марзулло (винайдений Кейтом Марзулло в рамках своєї кандидатської дисертації в 1984 році) — це алгоритм узгодження даних, що використовується для вибору більш точних джерел для оцінки точного часу з ряду джерел часу. Перероблена версія цього алгоритму, названа «алгоритмом перетинів», є частиною мережевого протоколу часу (NTP).

Мета

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

Припустимо, що ми маємо такі оцінки: 10 ± 2, 12 ± 1 і 11 ± 1 в інтервалах [8,12], [11,13] і [10,12]. Їх перетином буде інтервал [11,12] або точка 11.5 ± 0.5, що відповідає всім трьом джерелам.

Якщо натомість діапазони становлять [8,12], [11,13] та [14,15], то інтервал не відповідає всім цим значенням, але [11,12] відповідає найбільшій кількості джерел, а саме - двом.

Нарешті, якщо є діапазони [8,9], [8,12] та [10,12], то обидва інтервали [8,9] і [10,12] узгоджуються з найбільшою кількістю джерел. Ця процедура визначає інтервал. Якщо бажаний результат є найкращим значенням з цього інтервалу, тоді наївним підходом було б прийняти центр інтервалу як значення, яке було визначено в оригінальному алгоритмі Марзулло. Більш складний підхід визнав би, що це може викинути корисну інформацію з довірчих інтервалів джерел і що ймовірнісна модель джерел може повернути значення, відмінне від центру.

Зауважимо, що обчислене значення, ймовірно, краще характеризується як "оптимістичне", а не "оптимальне". Наприклад, розглянемо три інтервали [10,12], [11, 13] та [11,99,13]. Алгоритм, описаний нижче, обчислює [11,99, 12] або 11,995 ± 0,005, що є дуже точним значенням. Якщо ми підозрюємо, що одна з оцінок може бути невірною, то принаймні дві оцінки повинні бути правильними. За цієї умови найкраща оцінка є [11,13], оскільки це найбільший інтервал, який завжди перетинає щонайменше дві оцінки. Описаний нижче алгоритм легко параметризується з максимальною кількістю неправильних оцінок.

Метод

Алгоритм Марзулло починається з підготовки таблиці джерел, їх сортування та подальшого пошуку (ефективного) перетину інтервалів. Для кожного джерела існує діапазон [c − r, c + r], визначений c ± r. Для кожного діапазону таблиця матиме два кортежі форми <зміщення, тип>. Один кортеж представлятиме початок діапазону, позначений типом -1 як <c − r, −1>, а другий буде представляти кінець з типом +1 як <c + r, + 1>.

В описі алгоритму використовуються такі змінні: best (знайдена найбільша кількість інтервалів, що перекриваються), cnt (поточна кількість інтервалів, що перекриваються), beststart і bestend (початок і кінець найкращого інтервалу, знайденого поки що), i (index) , і стіл кортежів.

1. Побудуйте таблицю кортежів
2. Сортуйте таблицю за зміщенням. У разі однакового зміщення для двох кортежів протилежних типів (один інтервал закінчується початком іншого) застосувати спеціальний метод вирішення пріоритету. Такий випадок можна вважати перекриттям без тривалості, яке можна знайти за алгоритмом, поставивши тип -1 перед типом +1. Якщо такі патологічні перекриття вважаються заперечними, їх можна уникнути, поставивши тип +1 перед -1 у цьому випадку.)
3. [ініціалізувати] best = 0 cnt = 0
4. [цикл] проходьте кожен кортеж таблиці у порядку зростання.
5. [поточна кількість перекриваючих інтервалів] cnt = cnt-type [i]
6. якщо cnt > best тоді best = cnt beststart = offset[i] bestend = offset[i + 1]

коментар: наступний кортеж у [i + 1] буде або закінченням інтервалу (type = + 1); у цьому випадку він закінчує цей найкращий інтервал, або буде початком інтервалу (type = −1) і на наступному кроці замінить найкращий.неоднозначність: не визначено - що робити, якщо best = cnt. Це умова для найбільшого перекриття. Можна ухвалити рішення або взяти менше з bestend-beststart, або offset[i + 1] − offset[i], або просто взяти довільний один з двох однаково хороших записів.

7.[кінцевий цикл] повернути [beststart, bestend] як оптимальний інтервал. Кількість помилкових джерел (тих, які не перекривають оптимальний інтервал, що повертається) - це кількість джерел мінус значення кращих.

Список літератури

• Marzullo, K. A. (Feb 1984). Maintaining the Time in a Distributed System: An Example of a Loosely-Coupled Distributed Service. Ph.D. dissertation. Department of Electrical Engineering. Stanford University. ASIN B000710CSC. OCLC 38621764. DDC 3781.1984 M. Архів оригіналу за 19 жовтня 2019. Процитовано 19 жовтня 2019.