Sincronizador (algoritmo)

En informática , un sincronizador es un algoritmo que se puede utilizar para ejecutar un algoritmo síncrono sobre una red de procesadores asíncronos, lo que permite que el sistema asíncrono funcione como una red síncrona.

El concepto fue propuesto originalmente en (Awerbuch, 1985) junto con tres algoritmos de sincronización denominados alfa , beta y gamma , que ofrecían diferentes ventajas y desventajas en términos de tiempo y complejidad de mensajes. En esencia, constituyen una solución al problema de que los algoritmos asíncronos (que operan en una red sin reloj global) son más difíciles de diseñar y, a menudo, menos eficientes que los algoritmos síncronos equivalentes. Mediante el uso de un sincronizador, los diseñadores de algoritmos pueden trabajar con la "red ideal" simplificada y, posteriormente, generar mecánicamente una versión que opere en casos asíncronos más realistas.

Los tres algoritmos que Awerbuch proporcionó en su artículo original son los siguientes:

• Sincronizador alfa : Tiene una baja complejidad temporal pero una alta complejidad de mensajes.
• Sincronizador beta : Tiene una alta complejidad temporal pero una baja complejidad de mensajes.
• Sincronizador gamma : Este proporciona un equilibrio razonable entre alfa y beta al ofrecer una complejidad de mensajes y de tiempo bastante baja.

Desde la publicación del artículo original, se han propuesto otros algoritmos de sincronización en la literatura especializada.

• Baruch Awerbuch (1985). "Complejidad de la sincronización de redes" (PDF) .