Синхронизаторы и остовы: различия между версиями

Синхронизация сетей, остовные подграфы с низким коэффициентом растяжения

Рассмотрим коммуникационную сеть, моделируемую неориентированным взвешенным графом G = (V, E) с n вершинами, где n – целое положительное число. Каждая вершина G содержит процессор неограниченной вычислительной мощности; вершины имеют уникальные идентификационные номера и общаются друг с другом посредством дуг из G, пересылая друг другу сообщения размера O(log n).

В случае ''синхронной'' организации коммуникация осуществляется в виде дискретных ''раундов'', и сообщение, отправленное в начале раунда R, прибывает в точку назначения до его окончания. В случае ''асинхронной'' организации каждая вершина поддерживает собственный тактовый синхронизатор, причем у разных вершин они могут не совпадать. Предполагается, что каждое отправленное сообщение (в случае синхронной организации) прибывает в точку назначения в течение определенного временного интервала <math>\tau \;</math> после отправки, однако значение <math>\tau \;</math> процессорам неизвестно.

Авербух предложил три основных синхронизатора, назвав их <math>\alpha \;</math>, <math>\beta \;</math> и <math>\gamma \;</math>. Синхронизатор <math>\alpha \;</math> является самым простым; при его использовании накладные расходы по времени оказываются константными, однако по количеству коммуникаций – очень значительными. Точнее говоря, они являются линейными относительно количества ребер в сети, лежащей в основе системы. В отличие от синхронизатора <math>\alpha \;</math>, синхронизатору <math>\beta \;</math> требуется довольно дорогостоящий этап инициализации. Кроме того, его использование сопровождается значительными временными накладными расходами (линейными относительно количества вершин n), зато с точки зрения коммуникаций он более эффективен по сравнению с <math>\alpha \;</math>. Накладные расходы на коммуникации являются линейными относительно n.

Наконец, синхронизатор <math>\gamma \;</math> представляет собой нечто среднее между <math>\alpha \;</math> и <math>\beta \;</math>. Этот синхронизатор параметризован положительным целочисленным параметром k. Если значение k мало, то поведение синхронизатора схоже с поведением <math>\alpha \;</math>, а если велико – то он ведет себя подобно <math>\beta \;</math>. Особенно важным вариантом параметра k является k = log n. В этой точке кривая компромиссного выбора соответствует временным накладным расходам, логарифмическим относительно n и линейным относительно n издержкам синхронизации. Однако синхронизатор <math>\gamma \;</math> также требует весьма дорогостоящей инициализации.

Основной результат работы [1], относящийся к остовам, заключается в том, что для любого значения k = 1, 2, … и любого невзвешенного неориентированного графа G = (V, E) с n вершинами существует O(k)-остов с O(n1+1/k) ребрами. (Этот результат был развернут в работе Пелега и Шеффера [8]).

Синхронизаторы с улучшенными свойствами разработали Авербух и Пелег [3] и Авербух и др. [2]. И у тех, и у других накладные расходы по времени и коммуникациям являются полилогарифмическими. При этом синхронизаторы Авербуха и Пелега [3] требуют большого времени инициализации (в последнем случае оно по меньшей мере линейно относительно n). С другой стороны, синхронизаторы из [2] являются рандомизированными. Основной нерешенной задачей является получение ''детерминированных'' синхронизаторов с полилогарифмическими накладными расходами по времени и коммуникациям, с сублинейным относительно n временем инициализации. Кроме того, степени логарифма в выражении полилогарифмических накладных расходов по времени и коммуникациям в [2, 3] весьма высоки. Еще одной важной задачей является построение синхронизаторов с улучшенными параметрами.

Элкин и Пелег в [6] построили остовы, в которых большие расстояния искажаются значительно меньше, чем короткие. Этим остовам не удается обеспечить строго аддитивный уровень искажений. Построение остовов со строго аддитивным уровнем искажений остается главной нерешенной задачей.