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

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

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

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