Синхронизаторы и остовы

Ключевые слова и синонимы

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

Постановка задачи

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

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

В общем случае оказывается намного проще разрабатывать алгоритмы, рассчитанные на синхронную организацию (называемые синхронными алгоритмами), чем на асинхронную (соответственно, асинхронные). Авербух [1] инициировал исследование техник моделирования, которые переводили бы синхронные алгоритмы в асинхронные. Такие техники моделирования называются синхронизаторами.

При разработке первых синхронизаторов Авербух предложил определенное разбиение графа, представляющее интерес само по себе. В частности, Пелег и Шеффер [8] заметили, что это разбиение порождает подграф с определенными любопытными свойствами. Такой подграф они назвали остовом графа. Формально для целого положительного параметра k k-остовом графа G = (V, E) является подграф G' = (V, H), [math]\displaystyle{ H \subseteq E }[/math], такой, что для каждого ребра [math]\displaystyle{ e = (v, u) \in E \; }[/math] расстояние между вершинами v и u в H, [math]\displaystyle{ dist_{G'}(v, u) \; }[/math], не превышает k.

Основные результаты

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

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

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

Применение

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

Остовы графов оказались полезными для различных задач распределенных вычислений. В частности, они используются некоторыми видами синхронизаторов [1, 9]. Кроме того, остовы применяются для маршрутизации [4] и вычисления почти кратчайших путей в графах [5].

Открытые вопросы

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

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

См. также

• Разреженные остовы графов

Литература

1. Awerbuch, B.: Complexity of network synchronization. J. ACM 4,804-823(1985)

2. Awerbuch, B., Patt-Shamir, B., Peleg, D., Saks, M.E.: Adapting to asynchronous dynamic networks. In: Proc. of the 24th Annual ACM Symp. on Theory of Computing, Victoria, 4-6 May 1992, pp. 557-570

3. Awerbuch, B., Peleg, D.: Network synchronization with polylogarithmic overhead. In: Proc. 31 st IEEE Symp. on Foundations of Computer Science, Sankt Louis, 22-24 Oct. 1990, pp. 514-522

4. Awerbuch, B., Peleg, D.: Routing with polynomial communication-space tradeoff. SIAM J. Discret. Math. 5,151 -162 (1992)

5. Elkin, M.: Computing Almost Shortest Paths. In: Proc. 20th ACM Symp. on Principles of Distributed Computing, Newport, RI, USA, 26-29 Aug. 2001, pp. 53-62

6. Elkin, M., Peleg, D.: Spanner constructions for general graphs. In: Proc. of the 33th ACM Symp. on Theory of Computing, Heraklion, 6-8 Jul. 2001, pp. 173-182

7. Lakshmanan, K.B., Thulasiraman, K., Comeau, M.A.: An effi cient distributed protocol for finding shortest paths in networks with negative cycles. IEEE Trans. Softw. Eng. 15,639-644 (1989)

8. Peleg, D., Schaffer, A.: Graph spanners. J. Graph Theory 13, 99-116(1989)

9. Peleg, D., Ullman, J.D.: An optimal synchronizer for the hypercube. SIAM J. Comput. 18, 740-747 (1989)

10. Schieber, B., Moran, S.: Slowing sequential algorithms for obtaining fast distributed and parallel algorithms: Maximum matchings. In: Proc. of 5th ACM Symp. on Principles of Distributed Computing, Calgary, 11-13 Aug. 1986, pp. 282-292