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

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