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

Авербух предложил три основных синхронизатора, назвав их 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) ребрами. (Этот результат был развернут в работе Пелега и Шеффера [ ]).