Техника множественных испытаний - Multi-trials technique

В метод многократных испытаний Шнайдер и др. используется для распределенные алгоритмы и позволяет эффективно нарушать симметрию. Нарушение симметрии необходимо, например, в задачах распределения ресурсов, когда многие объекты хотят получить доступ к одному и тому же ресурсу одновременно. Много передача сообщений алгоритмы обычно используют одну попытку нарушения симметрии при обмене сообщениями. В метод многократных испытаний превосходит этот подход за счет использования большего количества попыток при каждом обмене сообщениями.[1]

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

Заметки

  1. ^ Шнайдер (2010)
  2. ^ Шнайдер (2008)

использованная литература

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