Синхронизатор (алгоритм)

В информатике синхронизатор алгоритм — это , который можно использовать для запуска синхронного алгоритма поверх асинхронной процессорной сети, что позволяет асинхронной системе работать как синхронная сеть.

Эта концепция была первоначально предложена в (Awerbuch, 1985) вместе с тремя алгоритмами синхронизатора, названными «альфа» , «бета» и «гамма» , которые обеспечивали различные компромиссы с точки зрения времени и сложности сообщения. По сути, они являются решением проблемы того, что асинхронные алгоритмы (которые работают в сети без глобальных часов) сложнее проектировать и часто менее эффективны, чем эквивалентные синхронные алгоритмы. Используя синхронизатор, разработчики алгоритмов могут работать с упрощенной «идеальной сетью», а затем механически создавать версию, которая работает в более реалистичных асинхронных случаях.

Доступные алгоритмы синхронизатора

Три алгоритма, которые Авербух представил в своей оригинальной статье, следующие:

• Альфа-синхронизатор : имеет низкую временную сложность, но высокую сложность сообщения.
• Бета-синхронизатор : имеет высокую временную сложность, но низкую сложность сообщений.
• Гамма-синхронизатор : обеспечивает разумный компромисс между альфа- и бета-версией, обеспечивая довольно низкое время и сложность сообщения.

Со времени выхода оригинальной статьи в литературе были предложены и другие алгоритмы синхронизатора.

Ссылки

• Барух Авербух (1985). «Сложность сетевой синхронизации» (PDF) .