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

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

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

В случае синхронной организации коммуникация осуществляется в виде дискретных раундов, и сообщение, отправленное в начале раунда R, прибывает в точку назначения до его окончания. В случае асинхронной организации каждая вершина поддерживает собственный тактовый синхронизатор, причем у разных вершин они могут не совпадать. Предполагается, что каждое отправленное сообщение (в случае синхронной организации) прибывает в точку назначения в течение определенного временного интервала x после отправки, однако значение т процессорам неизвестно.

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

При разработке первых синхронизаторов Авербух предложил определенное разбиение графа, представляющее интерес само по себе. В частности, Пелег и Шеффер [8] заметили, что это разбиение порождает подграф с определенными любопытными свойствами. Такой подграф они назвали остовом графа. Формально для целого положительного параметра k k-остовом графа G = (V, E) является подграф G0 = (V, H), H С E, такой, что для каждого ребра e = (v, u) 2 E расстояние между вершинами v и u в H, distG0(v, u), не превышает k.

Авербух предложил три основных синхронизатора, назвав их a, f$ и y. Синхронизатор a является самым простым; при его использовании накладные расходы по времени оказываются константными, однако по количеству коммуникаций – очень значительными. Точнее говоря, они являются линейными относительно количества ребер в сети, лежащей в основе системы. В отличие от синхронизатора a, синхронизатору f$ требуется довольно дорогостоящий этап инициализации. Кроме того, его использование сопровождается значительными временными накладными расходами (линейными относительно количества вершин n), зато с точки зрения коммуникаций он более эффективен по сравнению с a. Накладные расходы на коммуникации являются линейными относительно n.

Наконец, синхронизатор у представляет собой нечто среднее между a и f$. Этот синхронизатор параметризован положительным целочисленным параметром k. Если значение k мало, то поведение синхронизатора схоже с поведением a, а если велико – то он ведет себя подобно f$. Особенно важным вариантом параметра k является k = log n. В этой точке кривая компромиссного выбора соответствует временным накладным расходам, логарифмическим относительно n,и линейным относительно n издержкам синхронизации. Однако синхронизатор у также требует весьма дорогостоящей инициализации.

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

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

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

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

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