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

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

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