Синхронизаторы и остовы
Ключевые слова и синонимы
Синхронизация в сети, остовные подграфы с низким коэффициентом растяжения
Постановка задачи
Рассмотрим коммуникационную сеть, моделируемую неориентированным взвешенным графом 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
