Метод многократных испытаний

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

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

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

Эта статья, связанная с теорией графов, является заглушкой . Вы можете помочь Википедии, расширив ее.

• в
• т
• е