UNIVERSIDAD TÉCNICA PARTICULAR DE LOJA
SISTEMAS DISTRIBUIDOS
Entregable 2:
Exclusión mutua
Implementación de algoritmo de elección de líder
Integrantes:
Bravo Panchi Cristian Patricio
Montalván Castillo Rosa Isabel
Quezada Ortega Marlon Israel
Sandoval Sevilla Danny Leónidas
Sangines Vicuña Víctor Israel
Ing. Torres Tandazo Rommel Vicente
2022
1. Analice en detalle los algoritmos de elección de líder (Anillo, Bully) para su
posterior implementación. Cree un DFD para cada uno.
ALGORITMO DE ANILLO
Uso
Este algoritmo se usa cuando los procesos están física o lógicamente ordenados en
anillo, también en el caso de que no se conozcan el número total de procesos, o en el
caso de que cada proceso se comunica con su vecino (izquierda o derecha).
Aplicaciones
Elegir un nuevo servidor si se cae el actual.
Elegir un nuevo proceso para entrar en una sección crítica.
Elegir el proceso menos activo (balanceo de carga).
Elegir el proceso con la copia más reciente (réplicas).
Seguridad
El proceso elegido P es aquél con identificador mayor que no se ha caído hasta el
final de la ejecución del algoritmo de elección.
Pervivencia
La última vuelta asegura que todos los procesos activos conocen el resultado de la
elección.
Rendimiento
Ancho de banda: proporcional al número de mensajes enviados
Tiempo de ronda: tiempo pasado desde que se convocan elecciones hasta que se
elige un proceso
Procedimiento
Secuencia
1. Inicialmente todos los procesos son “no participantes”.
2. Cualquier proceso P decide arrancar una elección en cualquier momento.
3. Este proceso P se pone en estado “participante” y envía un mensaje de elección M a su
vecino.
4. El mensaje M enviado contiene el ID (identificador) del proceso que ha iniciado la elección.
5. Cuando el vecino recibe el mensaje de elección M, establece su estado como participante
y comprueba el ID del mensaje.
6. Si es mayor que su propio ID, entonces se lo envía directamente a su vecino.
7. Si su ID es mayor al ID recibido, entonces lo coloca en el mensaje M y lo envía a su vecino.
8. Así se circula el mensaje M sucesivamente hasta que llega a un proceso Pn que comprueba
que el ID recibido es el propio. Eso indica que solo ha sobrevivido el mayor ID, que es la del
proceso Pn.
9. Entonces, este proceso Pn es el coordinador y lo notifica a su vecino. Cuando un proceso
recibe un mensaje de coordinador debe de poner su estado como “no participante” y enviar
el mensaje a su vecino.
10. Cuando el mensaje de coordinador retorna al proceso que lo emitió (el coordinador),
entonces todos los procesos saben quién es el coordinador y todos quedan en estado “no
participantes”.
En caso de que dos procesos inicien al mismo tiempo una elección y se envíen mensajes de
elección, un proceso en estado de “participante” debe de verificar el ID del proceso que envía
el mensaje de elección. Si es menor al propio, el mensaje se descarta. Así, todos los mensajes
de elección se extinguirán, excepto el que lleva el ID más alto.
Diagrama de flujo algoritmo de anillo
ALGORITMO DE BULLY
El algoritmo del bully tiene como objetivo que el proceso con el identificador más alto se
seleccione como coordinador, tolerando fallas en el proceso, todo el proceso tiene un
identificador único conociendo los identificadores de otros procesos, por ende debe haber
una fase de descubrimiento o configuración, todos los procesos envían y conocen la ubicación
inicial de sus identificadores al resto del proceso, esta fase de descubrimiento se puede
requerir dependiendo de la cantidad de procesos que existan en el sistema, es aplicable
cuando los identificadores de los procesos no cambian, el algoritmo debe tener la capacidad
de detectar fallas, si no hay respuesta a una solicitud, por lo general los temporizadores y los
límites de tiempo se utilizan para los procesos.
El algoritmo utiliza tres tipos de mensajes:
Elección: enviado a los nodos candidatos con identificadores más altos.
Mensaje de respuesta: al proceso emisor y a los nodos con identificadores más bajos.
Coordinador: enviado por el proceso que está actuando o ha sido elegido líder.
Solo estos tres están permitidos.
Características.
Sirve para que ante la detección de un nodo caído se elija un nuevo líder.
El nodo que detecta que el nodo ha caído convoca a elecciones al resto de nodos.
El nuevo líder será elegido e base al identificador más alto.
Al momento de ser elegido el nodo comunicara al resto.
Protocolo de actuación
El algoritmo parte del estado en el que todos los procesos saben quién es el coordinador,
cada cierto tiempo se interroga al coordinador para saber si sigue vivo, si un proceso no
obtiene respuesta, manda a elección a todos los procesos con ID mayor, si ninguno responde
se convierte en coordinador automáticamente si recibe una respuesta OK espera a ver si le
llega un mensaje coordinador, si recibe un OK el proceso toma el rol de coordinador, si no se
repite el proceso de elección.
Diagrama de Contexto Nivel 0
El proceso remite la petición al coordinador para saber si está en funcionamiento, se notifica
el fallo y se procede a realizar la elección del nuevo coordinador.
Diagrama de Contexto Expandido
El proceso actual realiza la petición al coordinador, al no recibir respuesta notifica a los
procesos mayores, los procesos mayores realizan una petición al comprobar se realiza la
elección del nuevo coordinador con mayor ID
2. Implementación Algoritmo Anillo – Grupo 4
CODIGO JAVA CLIENTES – PROCESOS:
import [Link];
import [Link];
import [Link];
import [Link];
import [Link];
import [Link];
import [Link];
public class Process implements Runnable {
// The process socket
private static Socket processSocket = null;
// The output stream
private static PrintStream os = null;
// The input stream
private static DataInputStream is = null;
private static BufferedReader inputLine = null;
private static boolean closed = false;
public static void main(String[] args) {
// The default port.
int portNumber = 8091;
// The default host.
String host = "localhost";
if ([Link] < 2) {
[Link]("Iniciando en el host = " + host + ", Número de puerto = " + portNumber);
} else {
host = args[0];
portNumber = [Link](args[1]).intValue();
}
/* * Open a socket on a given host and port. Open input and output streams.*/
try {
processSocket = new Socket(host, portNumber);
inputLine = new BufferedReader(new InputStreamReader([Link]));
os = new PrintStream([Link]());
is = new DataInputStream([Link]());
} catch (UnknownHostException e) {
[Link]("No conocemos sobre el host " + host);
} catch (IOException e) {
[Link]("No se pudo obtener E/S para la conexión al host "
+ host);
}
/*
*If everything has been initialized then we want to write some data to the
socket we have opened a connection to on the port portNumber.
*/
if (processSocket != null && os != null && is != null) {
try {
/* Create a thread to read from the server. */
new Thread(new Process()).start();
while (!closed) {
[Link]([Link]().trim());
}
/* Closing the output stream, input stream,and the socket.*/
[Link]();
[Link]();
[Link]();
} catch (IOException e) {
[Link]("IOException: " + e);
}
}
}
/* Create a thread to read from the server.*/
//suppress warnings for [Link]() Depricated API
@SuppressWarnings("deprecation")
public void run() {
/* Keep on reading from the socket till we receive "Bye" from the
server. Once we received that then we want to break. */
String responseLine;
try {
while ((responseLine = [Link]()) != null) {
[Link](responseLine);
if ([Link]("***Bye") != -1)
break;
}
closed = true;
} catch (IOException e) {
[Link]("IOException: " + e);
}
}
}
CODIGO JAVA SERVIDOR:
import [Link];
import [Link];
import [Link];
import [Link].*;
import [Link];
import [Link];
import [Link];
import [Link];
/*
A server that delivers message between pairs of Processes.
*/
public class Server {
// The server socket.
private static ServerSocket serverSocket = null;
// The Process socket.
private static Socket processSocket = null;
// This server can accept up to maxProcessesCount Process connections.
private static int maxProcessesCount;
private static processThread[] threads;
public static void main(String args[]) {
Scanner sc=new Scanner([Link]);
[Link]("Ingrese el numero de procesos:");
maxProcessesCount=[Link]();
threads = new processThread[maxProcessesCount];
// The default port number.
int portNumber = 8091;
if ([Link] < 1) {
[Link]("Activo: Servidor Java, en uso puerto =" + portNumber);
} else {
portNumber = [Link](args[0]).intValue();
}
/* Open a server socket on the portNumber (default 8091). we can't use port less than 1023 if we are not
privileged users (root) and my port 80 is reserved for web so haven't used that either. */
try {
serverSocket = new ServerSocket(portNumber);
} catch (IOException e) {
[Link](e);
}
/* Creating a Process socket for each connection and pass it to a new Process thread. */
while (true) {
try {
processSocket = [Link]();
int i = 0;
for (i = 0; i < maxProcessesCount; i++) {
if (threads[i] == null) {
(threads[i] = new processThread(processSocket, threads)).start();
break;
}
}
if (i == maxProcessesCount) {
PrintStream os = new PrintStream([Link]());
[Link]("Procesos maximos alcanzados!!!"); //If we are creating more Processes then we have created
at the start on server
[Link]();
[Link]();
}
} catch (IOException e) {
[Link](e);
}
}
}
}
/*This processThread is created for each processes*/
class processThread extends Thread {
private int ProcessId;
private int previousProcessId;
private int nextProcessId;
private boolean initiator=false;
private boolean crashed=false;
private int coordinator;
private DataInputStream is = null;
private PrintStream os = null;
private Socket processSocket = null;
private final processThread[] threads;
private int maxProcessesCount;
public processThread(Socket processSocket, processThread[] threads) {
[Link] = processSocket;
[Link] = threads;
maxProcessesCount = [Link];
}
//suppress warnings for [Link]() Depricated API
@SuppressWarnings("deprecation")
public void run() {
int maxProcessesCount = [Link];
processThread[] threads = [Link];
try {
/* * Create input and output streams for this client. */
is = new DataInputStream([Link]());
os = new PrintStream([Link]());
String name,rname;
name="xyz";
rname="xyz";
while (true) {
[Link]("Ingrese su IP sin puntos:");
ProcessId = [Link]([Link]().trim());
[Link]("ProcessId:"+ProcessId);
break;
/* //Check if names are empty
if ([Link]("") || [Link]("")) {
[Link]("The name should not be empty.");
} else {
break;
}*/
}
synchronized (this) {
if(threads[maxProcessesCount-1]!=null)
{
[Link]("El algoritmo Anillo está formado por:");
for (int i = 0; i < maxProcessesCount; i++) {
if (threads[i] != null) {
[Link](threads[i].ProcessId);
if(i<(maxProcessesCount-1))
[Link]("-->");
}
}
}
}
[Link]("");
[Link]("");
[Link]("Ingrese INICIAR si deseas iniciar la elección");
[Link]("");
//this loop runs infinitely until user enters exit""
//This is to check the user input for different options and take actions accordingly
while (true) {
String line = [Link]();
if ([Link]("INICIAR")) //This does two jobs. first is to initiate the election and second is to give user an
option to initate when coordinator is crashed.
{
if([Link]) //This checks who sould initiate when coordinator is crashed
{
[Link]=false;
[Link]("");
[Link]("Iniciando la elección porque el lider está bloqueado.");
}
if([Link]) //This is the check for checking that process can't initiate if it is crashed
{
[Link]("Proceso esta bloqueado no puede iniciar la elección");
}
else //This initiates after all the checks are passed
{
int count=0;
for(int i=0;i<maxProcessesCount;i++)
{
if(threads[i].crashed)
count++;
}
int arrayCounter=0;
int tokenArray[]=new int[maxProcessesCount-count];
for (int i = 0; i < maxProcessesCount; i++) //Outer for loop for each process
{
if (threads[i] == this)
{
int k=0;
int j=0;
int crashcount=0;
for(j=i;j<maxProcessesCount-1;j++) //this loop runs from the initiation process to the end of the ring network
{
if(crashcount!=0)
{
crashcount=0;
continue;
}
int z=j+1;
while(threads[z+crashcount].crashed) //All the crashcount
while loops are to check the number of processes that are crashed from this process
{
crashcount++;
if(z+crashcount==maxProcessesCount)
z=-1;
}
if((j+1+crashcount)<maxProcessesCount)
{
tokenArray[arrayCounter]=threads[j].ProcessId;
arrayCounter++;
threads[j].nextProcessId=threads[j+1+crashcount].ProcessId;
try{
[Link](3000); //To give a delay of 3000ms between transmitting tokens
}
catch(Exception e)
{
}
threads[j+1+crashcount].previousProcessId=threads[j].ProcessId;
try{
[Link](3000);
}
catch(Exception e)
{
}
}
else
{
tokenArray[arrayCounter]=threads[j].ProcessId;
arrayCounter++;
threads[j].nextProcessId=threads[0+crashcount-1].ProcessId;
try{
[Link](3000);
}
catch(Exception e)
{
}
threads[0+crashcount1].previousProcessId=threads[j].ProcessId;
try{
[Link](3000);
}
catch(Exception e)
{
}
}
}
//The code ahead is to send tokens from this last process to first process
k=j;
crashcount=0;
if(threads[k].crashed)
{
}
else
{
while(threads[0+crashcount].crashed)
{
crashcount++;
}
tokenArray[arrayCounter]=threads[k].ProcessId;
arrayCounter++;
threads[k].nextProcessId=threads[0+crashcount].ProcessId;
try{
[Link](3000);
}
catch(Exception e)
{
}
threads[0+crashcount].previousProcessId=threads[k].ProcessId;
try{
[Link](3000);
}
catch(Exception e)
{
}
}
for(j=0;j<i;j++) //This is to send tokens from first process to the initiation process
{
crashcount=0;
if(threads[j].crashed)
{
continue;
}
while(threads[j+1+crashcount].crashed)
{
crashcount++;
}
tokenArray[arrayCounter]=threads[j].ProcessId;
arrayCounter++;
try{
[Link](3000);
}
catch(Exception e)
{
}
try{
[Link](3000);
}
catch(Exception e)
{
}
}
}
}
int maxCoordinator=0;
for(int i=0;i<[Link];i++)
{
if(tokenArray[i]>maxCoordinator)
maxCoordinator=tokenArray[i];//to select the highest process as coordinator hence this for loop gets the max of all
the processes.
}
[Link]("Proceso con Id: "+maxCoordinator+" es el nuevo lider");
//sending the new Coordinator message
for (int i = 0; i < maxProcessesCount; i++)//This for loop iterates only through uncrashed
process and send them again the message who is the current coordinator
{
threads[i].coordinator=maxCoordinator;
if (threads[i] == this)
{
int k=0;
int j=0;
int crashcount=0;
for(j=i;j<maxProcessesCount-1;j++)
{
if(crashcount!=0)
{
crashcount=0;
continue;
}
int z=j+1;
while(threads[z+crashcount].crashed)
{
crashcount++;
if(z+crashcount==maxProcessesCount)
z=-1;
}
if((j+1+crashcount)<maxProcessesCount)
{
threads[j+1+crashcount].[Link]("Proceso con Id: "+maxCoordinator+" es el nuevo lider.");
try{
[Link](3000);
}
catch(Exception e)
{
}
}
else
{
threads[0+crashcount-1].[Link]("Proceso con Id: "+maxCoordinator+" es el nuevo lider.");
try{
[Link](3000);
}
catch(Exception e)
{
}
}
}
k=j;
crashcount=0;
if(threads[k].crashed)
{
}
else
{
while(threads[0+crashcount].crashed)
{
crashcount++;
}
threads[0+crashcount].[Link]("Proceso con Id: "+maxCoordinator+" es el nuevo lider");
try{
[Link](3000);
}
catch(Exception e)
{
}
}
for(j=0;j<i;j++)
{
crashcount=0;
if(threads[j].crashed)
{
continue;
}
while(threads[j+1+crashcount].crashed)
{
crashcount++;
}
threads[j+1+crashcount].[Link]("Proceso con Id: "+maxCoordinator+" es el nuevo lider");
try{
[Link](3000);
}
catch(Exception e)
{
}
}
}
}
}
}else if([Link]("BLOQUEAR")) //This is to crash the current processes for both process and
coordinator
{
[Link]=true;
if([Link]==[Link])
{
[Link]("Lider bloqueado");
for(int i=0;i<maxProcessesCount;i++)
{
if(threads[i].ProcessId==[Link])
{
threads[i].initiator=true;
threads[i].[Link]("Por favor inicie la elección porque el lider se encuentra bloqueado");
}
}
}
else{
[Link]("Process is crashed");
}
}
else if([Link]("RECUPERAR")) //This is to recover the crashed Process
{
[Link]=false;
[Link]("Proceso recuperado");
}
else if([Link]("quit")) //This is to quit the execution
{
break;
}
else //This checks whether user entered invalid input
{
[Link]("Invalid Input");
}
}
/*
Close the output stream, close the input stream, close the socket.
*/
[Link]();
[Link]();
[Link]();
} catch (IOException e) {
}
}
}
3. Verifique su funcionamiento con al menos un cliente por estudiante. Cada
estudiante debe hacer captura de tráfico de su consola o IDE donde se refleje la
ejecución del programa.
Cliente: Rosa Montalvan
Cliente: Marlon Quezada
Cliente: Danny Sandoval
Cliente: Victor Sanguines
Servidor: Cristian Bravo
4. Capture tráfico con Wireshark para determinar la elección de líder. Haga una
serie de capturas de pantalla donde se demuestre la interacción de los
compañeros a través de sus direcciones IP. Se sugiere colocar en el documento
una tabla con las direcciones IP del equipo de cada cliente/compañero.
DIRECCIONES IP
ROL IP INTEGRANTE
SERVIDOR [Link] BRAVO CRISTIAN
[Link] MONTALVAN ROSA
[Link] QUEZADA MARLON
CLIENTES
[Link] SANDOVAL DANNY
[Link] SANGINES VICTOR
5. Redacte sus conclusiones considerando el tiempo y la cantidad de
interacciones en el cual el algoritmo eligió al líder. Así como también cuál ha
sido la experiencia del grupo en lograr la elección con su algoritmo.
El algoritmo de elección basado en anillo está formado por un sistema de procesos
interconectados en secuencia hasta lograr formar y cerrar el anillo entre todos los
procesos, en donde el intercambio de mensajes se realiza en el sentido de reloj.
El algoritmo de elección basado en anillo está definido a identificar el líder del sistema
de acuerdo con su identificador, el mismo que debe ser mayor a los demás procesos
y puede ser un valor en acuerdo y conocimiento hacia todos los procesos que
conformen el sistema como; un valor simple, la dirección IP, o un numero compuesto.
El algoritmo de Bully garantiza la existencia de un coordinador único en un conjunto
de procesos, en el cual todos los procesos pueden estar de acuerdo, aunque alguno
de ellos puede fallar.
Dentro de sus premisas cada proceso tiene un único identificador, y los procesos
almacenan el identificador del proceso coordinador actual y este algoritmo garantiza
que todos los procesos tengan el mismo coordinador el mismo que está operativo y
con el identificador más alto.
Al desarrollo del código Java, por una parte, se indica la ejecución del cliente, siendo
cada uno de los procesos que forman parte del anillo en formación hacia la elección
de un líder, en otro aspecto el código de control está asignado como un servidor quien
ejecuta la parte lógica del código en referencia al algoritmo Anillo.
En la presente practica la codificación facilita determinar el número de procesos que
formarían parte del Anillo, una vez ejecutado cada uno de los procesos irán formando
parte del anillo y de acuerdo al orden de ejecución se irán entrelazando para su
respectiva comunicación.
Para determinar el proceso con su identificador más alto, después de ejecutar el
código de forma individual de cada cliente se proyecta en consola el requerimiento de
ingresar su IP sin puntos, para lo cual acortar su comparación fueron ingresados los
dos últimos números de la IP de cada cliente, de tal forma se comparan los valores
entre todos los procesos integrantes y será seleccionado como líder el de mayor valor,
siendo en este caso destinado la dirección IP [Link], ya que su valor de 97 es
mayor a los demás.
6. Bibliografía:
Emmanuel, C. C. (2015). Algoritmo de anillo (Elección Distribuida). Obtenido de Facultad
deIngeniería, UNAM.: [Link]
Salguero, E. (03 de MARZO de 2018). Sistemas distribuidos: coordinación y acuerdo (II).
Obtenido de [Link]: [Link]
distribuidos-coordinacion-y-acuerdo-aa0b18b444e7
Santamaría, R. (s.f.). Sistemas Distribuidos Coordinación y acuerdo. Obtenido de chrome-
extension://efaidnbmnnnibpcajpcglclefindmkaj/[Link]
isdis/teoria/[Link]
