Sincronismo

Un algoritmo es sincrónico si sus acciones pueden ser delimitadas en el tiempo

• Sincrónico: Entrega de un mensaje posee un timeout conocido.
• Parcialmente sincrónico: Entrega de un mensaje no posee un timeout conocido o bien el mismo es variable.
• Asincrónico: Entrega de un mensaje no posee un timeout asociado.

Propiedades

Esto se generaliza en dos propiedades: steadiness y tightness.

Antes de definirlas, debemos definir dos conceptos auxiliares:

• Tiempo de delivery $t_D^P(m)$: Es el tiempo que tarda un mensaje $m$ en ser recibido por $p$, una vez enviado.
• Timeout de delivery $T_{D\max }(m)$: Es el tiempo de delivery máximo, para un mensaje $m$.

Luego, podemos definir el steadiness $\sigma$ como la máxima diferencia tiempo de delivery de cualquier mensaje recibido por un solo proceso.

$$\sigma =\max (t_{D\max }-t_{D\min })$$

Define la varianza con la cual un proceso observa que recibe los mensajes, y muestra que tan constante es la recepción de mensaje.

Por otro lado, el tightness como la máxima diferencia entre los tiempos de delivery para un mensaje dado, hacia todos los procesos.

$$\forall p,q:\tau =\underset{m,p,q}{\max }(t_D^p(m)-t_D^q(m))$$

Define la simultaneidad con la cual un mensaje es recibido por múltiples procesos.

Tipos de Protocolos

En un protocolo Time-Driven, las fases del protocolo están definidas por un factor de tiempo entre mensajes.

En este ejemplo, vemos que el proceso $P_1$ envía mensaje al resto de procesos. Al haber un timeout conocido (algoritmo sincrónico), si no le llega el $ack$ tras un tiempo $T_{D\max }$, entonces el mensaje se vuelve a enviar. No hay garantía de que a los procesos les llegue el mensaje al mismo tiempo.

En un protocolo Clock-Driven, las fases del protocolo están definidas por el reloj de cada proceso. Los mensajes se pueden recibir antes, pero el delivery ocurre en una fracción de tiempo determinada.

En este ejemplo, vemos que el proceso $P_1$ envía un mensaje $m$ al resto de procesos, que incluye el timestamp de $P_1$. El delivery del mensaje solo se hará tras un tiempo $t+\Delta$. De esta forma, nos aseguramos un cierto steadiness y tightness. Esto requiere que el reloj de los procesos estén sincronizados.

En este otro ejemplo, vemos como los mensajes se envían en time slots puntuales. Esto nuevamente nos asegura un cierto steadiness y tightness, ya que el delivery de los mensajes se retrasa utilizando información del los relojes.