Algoritmo de onda y recorrido en sistema distribuido

Como sabemos, un sistema distribuido es una colección donde diferentes procesos con el fin de realizar una tarea se comunican entre sí. En el algoritmo de onda se produce el intercambio de mensajes y la decisión, que depende del número de mensajes en cada evento de un proceso. Como es importante atravesar una red conectada, el algoritmo Wave tiene aplicaciones en muchos campos, como bases de datos distribuidas , redes inalámbricas, etc.  

Notación:

• Los cálculos (C) en un proceso se denotan ICI
• Cualquier subconjunto del proceso (p) en computación (C) se denota como C _p .
• El conjunto de todos los procesos se denota por P’,
• El conjunto de canales de E.
• El Node desde donde se inicia el proceso se denomina Iniciadores o starters.
• Cualquier Node no iniciador en una red llamada seguidores.
• El evento de un iniciador es enviar evento
• El evento de un no iniciador ha recibido el evento.

Algoritmo de onda:

Un algoritmo que satisface los tres requisitos se considera un algoritmo de onda en un algoritmo distribuido:

• Terminación: Cada cálculo es finito.
  • ∀C : lC| < ∞
• Decisión: cada cálculo contiene al menos un evento de decisión.
  • ∀C: ∃e ∈ C: e es un evento decisivo.
• Dependencia: En cada cómputo, cada evento decidido es casualmente precedido por un evento en cada proceso.
  • ∀C: ∀e ∈ C : (e es un evento decisivo ⇒ ∀q ∈ P’ ∃f ∈C _q : f ≥ e).

Un algoritmo de onda parte de un proceso particular y la onda se propaga a sus vecinos, y los vecinos se propagan a sus vecinos, y así sucesivamente. Cuando no hay más Nodes para propagar, la onda regresa.

La fuerza del Algoritmo de Onda radica en la Comunicación asincrónica donde existe una equivalencia entre las strings casual y de mensaje. En los algoritmos de ondas, se requiere la existencia de strings de mensajes para el cálculo de la dependencia causal. Los algoritmos de ondas pueden diferir entre sí en función de las siguientes propiedades:

• Centralización: los algoritmos se diferencian entre sí si tienen un iniciador o más de un iniciador.
  • Un algoritmo tiene exactamente un iniciador en cada cálculo se llama centralizado,
  • Si el algoritmo puede ser iniciado espontáneamente por un subconjunto arbitrario de los procesos llamados descentralizados.
• Conocimiento Inicial: Un algoritmo se diferencia entre sí si tienen conocimiento inicial en los procesos.
  • Identidad del proceso: cada proceso tiene su nombre único.
  • Identidad del Vecino: Cada proceso conoce el nombre de su vecino.
• Complejidad: La complejidad del algoritmo considera
  • el número de mensajes intercambiados
  • el número de bits intercambiados,
  • el tiempo necesario para un cálculo.

Propiedades de las ondas:

• Cada evento en el cálculo está precedido por un evento en un iniciador.
• Un algoritmo de ondas para redes arbitrarias sin conocimiento inicial de las identidades de los vecinos. Luego, el algoritmo intercambia al menos mensajes lEI en cada cálculo.

Dado que la propagación de paquetes se realiza mediante la red de ondas de Nodes y puede tratarse como una relación de orden parcial, 

Ahora, considere una relación binaria ≤ _* por x ≤ _* y ⇐⇒ (x * y) = x, es decir; en la relación ≤* es un orden parcial sobre X, es decir, que esta relación es transitiva, antisimétrica y reflexiva.

• Transitividad : sabemos que x≤ y y y≤ z entonces x≤ z, supongamos que x ≤ _* y y y ≤ _* z; por definición de ≤ _* , (x*y) = x y (y*z) = y. Usando estos y la asociatividad encontramos (x * z) = (x * y) * z = x * (y * z) = x * y = x, es decir, x ≤ _* z.
• Antisimetría : Suponga que x ≤ _* yey ≤ _* x; por definición de ≤ _* , x * y = x y y * x = y. Usando estos y la conmutatividad encontramos x = y.
• Reflexividad : x * x = x, es decir, x ≤ _* x, la propiedad reflexiva se puede probar usando la idempotencia.

Dado que satisface las tres propiedades, concluimos que el algoritmo de onda puede tratarse como una relación de orden parcial.

Algoritmo de onda diferente:

El Algoritmo de Anillo: El canal para la propagación del proceso se selecciona de manera que forme un ciclo hamiltoniano (todos los Nodes atravesados). En otras palabras, el proceso (p) y su vecino (Next _p ) se dan de tal manera que los canales seleccionados de esta manera forman un ciclo hamiltoniano (todos los Nodes atravesados).

• Tiene un solo iniciador.
• Cada otro Node pasa el mensaje hacia adelante.
• El algoritmo de anillo está centralizado.
• El iniciador es el Node que decide.

For initiator-
begin 
     send (tok) to Nextp;
     receive (tok);
     decide;
end

Ring algorithm for non initiator-
begin
     receive (tok);
     send (tok) to Nextp;
end

El algoritmo de sondeo:  el algoritmo enviará una onda que llegará a todos los Nodes y volverá al originador y cuando la onda disminuya, el algoritmo terminará.

• Funciona en una red de camarilla.
• Tiene un solo iniciador.
• El algoritmo de sondeo está centralizado.
• El iniciador es el Node que decide.

En el algoritmo de sondeo, el iniciador le pide a cada vecino que responda con un mensaje y decide después de recibir todos los mensajes.

Polling algorithm for Initiator-

var recp: integer init 0;
begin
     for all q Neighp
do send (tok)to qf;
     while recp<#Neighp do
          begin
               receive(tok);
               recp:= recp + 1;
          end
      decide
    end
// here recp is used as a count variable

Polling algorithm for non Initiator-
begin
     receive (tok)from qf;
     send (tok) to q;
end

El sondeo también se puede utilizar en una red en estrella en la que el iniciador es el centro.

Nota: el algoritmo de onda se utiliza para todas las tareas fundamentales, es decir, funciones globales de transmisión, sincronización y computación.

 Algoritmo transversal: 

Los algoritmos de onda tienen las siguientes dos propiedades adicionales:

• el iniciador es el único proceso que decide
• todos los eventos están ordenados totalmente por el participante en orden de causa-efecto.

Los algoritmos de ondas con estas propiedades se denominan algoritmos transversales. o Traversal Algorithm si cumple estas propiedades:

• En cada cálculo, hay un iniciador, que inicia el algoritmo enviando exactamente un mensaje
• Un proceso, al recibir un mensaje, envía un mensaje o decide.
• Cada proceso ha enviado un mensaje al menos una vez, luego el algoritmo termina en el iniciador.

Ejemplo de algoritmo de desplazamiento:

Algoritmo de sondeo secuencial: El algoritmo de sondeo secuencial es lo mismo que el algoritmo de sondeo.

• Un vecino es encuestado a la vez.
• El vecino siguiente se sondea solo cuando se recibe la respuesta de un vecino anterior.

Sequential Polling algorithm for Initiator-
var recp: integer init 0;
begin
     while recp<#Neighp do
          begin
               send(tok)to qrecp+1;
               receive(tok);
               recp:= recp + 1;
          end;
      decide
    end

Sequential Polling algorithm for non Initiator-
begin
     receive (tok)from q;
     send (tok) to q;
end

Nota: Los algoritmos transversales se utilizan para construir algoritmos de elección.

Topología:

• Anillo: Es una estructura de red circular donde cada red está conectada con exactamente dos redes.
• Árbol: Es un tipo de topología jerárquica donde la red raíz está conectada a todas las demás redes y hay un mínimo de tres niveles de jerarquía.
• Clique: El canal de red está presente entre cada par de procesos.

Las métricas para medir la eficiencia de los algoritmos son:

• La complejidad del tiempo es el número de mensajes en la string más larga.
• La complejidad del mensaje es el número de mensajes llevados a cabo por un algoritmo.

Aquí hay una tabla que muestra diferentes algoritmos con sus propiedades:

• N es el número de procesos
• lEI el número de canales
• D el diámetro de la red (en saltos).
• DFS – Primera búsqueda en profundidad

S. No.	Algoritmo	Topología	Centralizado(C)/ Descentralizado (D)	Atravesando	Complejidad del mensaje (M)	Complejidad del tiempo
01.	Anillo	anillo	C	no	norte	norte
02	Árbol	árbol	D	no	norte	SOBREDOSIS)
03.	Eco	arbitrario	C	no	2|E|	EN)
04.	Votación	camarilla	C	no	2N-2	2
05.	finlandés	arbitrario	D	no	<=4.N.|E|	SOBREDOSIS)
06	Sondeo de secuencia	camarilla	C	sí	2N-2	2N-2
07	DFS clásico	arbitrario	C	sí	2|E|	2|E|