Техника многократных попыток

Методика множественных испытаний Schneider et al. используется для распределенных алгоритмов и позволяет эффективно нарушать симметрию. Нарушение симметрии необходимо, например, в задачах распределения ресурсов, когда множество объектов хотят одновременно получить доступ к одному и тому же ресурсу. Многие алгоритмы передачи сообщений обычно используют одну попытку нарушения симметрии для каждого обмена сообщениями. Техника множественных попыток превосходит этот подход, поскольку при каждом обмене сообщениями используется больше попыток.

Например, в простом алгоритме вычисления раскраски вершин O(Δ) , где Δ обозначает максимальную степень в графе, каждый неокрашенный узел случайным образом выбирает доступный цвет и сохраняет его, если ни один сосед (одновременно) не выбирает тот же цвет. В методе множественных испытаний узел постепенно увеличивает количество выбранных цветов в каждом раунде связи. Этот метод может привести к более чем экспоненциальному сокращению количества необходимых раундов связи. Однако, если максимальная степень Δ мала, существуют более эффективные методы, например, (расширенная) техника подбрасывания монеты Ричарда Коула и Узи Вишкина .

Ссылки

• Шнайдер, Дж. (2010), «Новый метод нарушения распределенной симметрии» (PDF) , Материалы симпозиума по принципам распределенных вычислений
• Шнайдер, Дж. (2008), «Алгоритм максимального независимого множества с распределенным лог-звездой для графов с ограниченным ростом» (PDF) , Труды симпозиума по принципам распределенных вычислений