¿Cómo podría evitar un punto muerto distribuido durante una conexión mutua entre dos nodos?

Supongamos que tenemos dos nodos pares: el primer nodo puede enviar una solicitud de conexión al segundo, pero también el segundo puede enviar una solicitud de conexión al primero. ¿Cómo evitar una doble conexión entre los dos nodos? Para resolver este problema, sería suficiente realizar las operaciones secuenciales para crear conexiones TCP entrantes o salientes.

Esto significa que cada nodo debe procesar secuencialmente cada nueva operación de creación de conexión, tanto para conexiones entrantes como para conexiones salientes. De esta manera, manteniendo una lista de nodos conectados, antes de aceptar una nueva conexión entrante desde un nodo o antes de enviar una solicitud de conexión a un nodo, será suficiente verificar si este nodo ya está presente en la lista.

Para realizar las operaciones secuenciales de creación de conexiones, es suficiente realizar un bloqueo en la lista de nodos conectados: de hecho, para cada nueva conexión, el identificador del nuevo nodo conectado se agrega a esta lista. Sin embargo, me pregunto si este enfoque puede causar un punto muerto distribuido :

• el primer nodo podría enviar una solicitud de conexión al segundo;
• el segundo nodo podría enviar una solicitud de conexión al primero;
• Suponiendo que las dos solicitudes de conexión no son asíncronas, ambos nodos bloquean las solicitudes de conexión entrantes.

¿Cómo podría resolver este problema?

ACTUALIZACIÓN: Sin embargo, todavía tengo que bloquear la lista cada vez que se crea una nueva conexión (entrante o saliente), ya que otros subprocesos pueden acceder a esta lista, entonces el problema de punto muerto aún persiste.

ACTUALIZACIÓN 2: Basado en su consejo, escribí un algoritmo para evitar la aceptación mutua de una solicitud de inicio de sesión. Como cada nodo es un par, podría tener una rutina de cliente para enviar nuevas solicitudes de conexión y una rutina de servidor para aceptar conexiones entrantes.

ClientSideLoginRoutine() {
    for each (address in cache) {
        lock (neighbors_table) {
            if (neighbors_table.contains(address)) {
                // there is already a neighbor with the same address
                continue;
            }
            neighbors_table.add(address, status: CONNECTING);

        } // end lock

        // ...
        // The node tries to establish a TCP connection with the remote address
        // and perform the login procedure by sending its listening address (IP and port).
        boolean login_result = // ...
        // ...

        if (login_result)
            lock (neighbors_table)
                neighbors_table.add(address, status: CONNECTED);

    } // end for
}

ServerSideLoginRoutine(remoteListeningAddress) {
    // ...
    // initialization of data structures needed for communication (queues, etc)
    // ...

    lock(neighbors_table) {
        if(neighbors_table.contains(remoteAddress) && its status is CONNECTING) {
            // In this case, the client-side on the same node has already
            // initiated the procedure of logging in to the remote node.

            if (myListeningAddress < remoteListeningAddress) {
                refusesLogin();
                return;
            }
        }
        neighbors_table.add(remoteListeningAddress, status: CONNECTED);

    } // end lock
}

Ejemplo: La IP: puerto del nodo A es A: 7001 - La IP: puerto del nodo B es B: 8001.

Supongamos que el nodo A ha enviado una solicitud de inicio de sesión al nodo B: 8001. En este caso, el nodo A llama a la rutina de inicio de sesión enviando enviando su propia dirección de escucha (A: 7001). Como consecuencia, la tabla de vecinos del nodo A contiene la dirección del nodo remoto (B: 8001): esta dirección está asociada con el estado de CONEXIÓN. El nodo A está esperando que el nodo B acepte o rechace la solicitud de inicio de sesión.

Mientras tanto, el nodo B también puede haber enviado una solicitud de conexión a la dirección del nodo A (A: 7001), luego el nodo A puede estar procesando la solicitud del nodo B. Entonces, la tabla de vecinos del nodo B contiene la dirección del control remoto nodo (A: 7001): esta dirección está asociada con el estado de CONEXIÓN. El nodo B está esperando que el nodo A acepte o rechace la solicitud de inicio de sesión.

Si el lado del servidor del nodo A rechaza la solicitud de B: 8001, entonces debo estar seguro de que el lado del servidor del nodo B aceptará la solicitud de A: 7001. Del mismo modo, si el lado del servidor del nodo B rechaza la solicitud de A: 7001, entonces debo estar seguro de que el lado del servidor del nodo A aceptará la solicitud de B: 8001.

De acuerdo con la regla de "dirección pequeña" , en este caso el nodo A rechazará la solicitud de inicio de sesión del nodo B, mientras que el nodo B aceptará la solicitud del nodo A.

¿Qué piensas sobre eso?

Puede probar un enfoque "optimista": conéctese primero, luego desconéctese si detecta una conexión mutua concurrente. De esta manera, no necesitaría excluir las solicitudes de conexión mientras realiza nuevas conexiones: cuando se establece una conexión entrante, bloquee la lista y vea si tiene una conexión saliente con el mismo host. Si lo hace, verifique la dirección del host. Si es más pequeño que el suyo, desconecte su conexión saliente; de lo contrario, desconecte el entrante. Su host igual hará lo contrario, porque las direcciones se compararán de manera diferente, y una de las dos conexiones se cortará. Este enfoque le permite evitar volver a intentar sus conexiones y potencialmente lo ayuda a aceptar más solicitudes de conexión por unidad de tiempo.

Cuando un nodo envía una solicitud a otro, podría incluir un entero aleatorio de 64 bits. Cuando un nodo recibe una solicitud de conexión, si ya ha enviado uno propio, mantiene el que tiene el número más alto y descarta los demás. Por ejemplo:

Tiempo 1: A intenta conectarse a B, envía el número 123.

Tiempo 2: B intenta conectarse a A, envía el número 234.

Tiempo 3: B recibe la solicitud de A. Dado que la solicitud de B tiene un número mayor, niega la solicitud de A.

Tiempo 4: A recibe la solicitud de B. Como la solicitud de B tiene un número mayor, A la acepta y descarta su propia solicitud.

Para generar el número aleatorio, asegúrese de sembrar su generador de números aleatorios con / dev / urandom, en lugar de utilizar la distribución predeterminada de su generador de números aleatorios, que a menudo se basa en el tiempo del reloj de pared: existe una posibilidad no ignorable de que dos nodos obtendrá la misma semilla.

En lugar de números aleatorios, también podría distribuir números con anticipación (es decir, numerar todas las máquinas del 1 al n), o usar una dirección MAC, o alguna otra forma de encontrar un número donde la probabilidad de colisión sea tan pequeña como para ser ignorable

Si entiendo, el problema que estás tratando de evitar es el siguiente:

• El nodo 1 solicita la conexión del nodo 2
• Nodo1 bloquea la lista de conexiones
• El nodo 2 solicita la conexión del nodo 1
• Nodo2 bloquea la lista de conexiones
• El nodo 2 recibe la solicitud de conexión del nodo 1, rechaza porque la lista está bloqueada
• El nodo 1 recibe la solicitud de conexión del nodo 2, rechaza porque la lista está bloqueada
• Ninguno de los dos termina conectándose entre sí.

Puedo pensar en un par de formas diferentes de lidiar con esto.

1. Si intenta conectarse a un nodo y rechaza su solicitud con un mensaje de "lista bloqueada", espere un número aleatorio de milisegundos antes de volver a intentarlo. (La aleatoriedad es crítica. Hace que sea mucho menos probable que ambos esperen exactamente la misma cantidad de tiempo y repitan el mismo problema hasta el infinito ).
2. Sincronice los relojes de ambos sistemas con un servidor de hora y envíe una marca de tiempo junto con la solicitud de conexión. Si llega una solicitud de conexión desde un nodo al que está intentando conectarse actualmente, ambos nodos están de acuerdo en que el que intente conectarse primero gana y la otra conexión se cierra.