Comment pourrais-je éviter un blocage distribué lors d'une connexion mutuelle entre deux nœuds?

Supposons que nous ayons deux nœuds homologues: le premier nœud peut envoyer une demande de connexion au second, mais également le second peut envoyer une demande de connexion au premier. Comment éviter une double connexion entre les deux nœuds? Pour résoudre ce problème, il suffirait de rendre séquentielles les opérations effectuées pour créer des connexions TCP entrantes ou sortantes.

Cela signifie que chaque nœud doit traiter séquentiellement chaque nouvelle opération de création de connexion, à la fois pour les connexions entrantes et pour les connexions sortantes. De cette façon, en conservant une liste de nœuds connectés, avant d'accepter une nouvelle connexion entrante d'un nœud ou avant d'envoyer une demande de connexion à un nœud, il suffira de vérifier si ce nœud est déjà présent dans la liste.

Pour rendre séquentielles les opérations de création de connexions, il suffit d'effectuer un verrouillage sur la liste des nœuds connectés: en effet, pour chaque nouvelle connexion, l'identifiant du nouveau nœud connecté est ajouté à cette liste. Cependant, je me demande si cette approche peut provoquer un blocage distribué :

• le premier nœud pourrait envoyer une demande de connexion au second;
• le deuxième nœud pourrait envoyer une demande de connexion au premier;
• en supposant que les deux demandes de connexion ne sont pas asynchrones, les deux nœuds verrouillent toutes les demandes de connexion entrantes.

Comment pourrais-je résoudre ce problème?

MISE À JOUR: Cependant, je dois toujours verrouiller la liste chaque fois qu'une nouvelle connexion (entrante ou sortante) est créée, car d'autres threads peuvent accéder à cette liste, alors le problème de blocage resterait.

MISE À JOUR 2: Sur la base de vos conseils, j'ai écrit un algorithme pour empêcher l'acceptation mutuelle d'une demande de connexion. Étant donné que chaque nœud est un homologue, il pourrait avoir une routine client pour envoyer de nouvelles demandes de connexion et une routine serveur pour accepter les connexions 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
}

Exemple: Le port IP: du nœud A est A: 7001 - Le port IP: du nœud B est B: 8001.

Supposons que le nœud A a envoyé une demande de connexion au nœud B: 8001. Dans ce cas, le nœud A appelle la routine de connexion en envoyant en envoyant sa propre adresse d'écoute (A: 7001). En conséquence, la table voisins_ du nœud A contient l'adresse du nœud distant (B: 8001): cette adresse est associée à l'état CONNECTING. Le nœud A attend que le nœud B accepte ou refuse la demande de connexion.

Pendant ce temps, le nœud B peut également avoir envoyé une demande de connexion à l'adresse du nœud A (A: 7001), puis le nœud A peut traiter la demande du nœud B. Ainsi, la table_voisins du nœud B contient l'adresse de la télécommande nœud (A: 7001): cette adresse est associée à l'état CONNECTING. Le nœud B attend que le nœud A accepte ou refuse la demande de connexion.

Si le côté serveur du nœud A rejette la demande de B: 8001, je dois être sûr que le côté serveur du nœud B acceptera la demande de A: 7001. De même, si le côté serveur du nœud B rejette la demande de A: 7001, je dois être sûr que le côté serveur du nœud A acceptera la demande de B: 8001.

Selon la règle de la "petite adresse" , dans ce cas, le nœud A rejettera la demande de connexion par le nœud B, tandis que le nœud B acceptera la demande du nœud A.

Qu'est ce que tu penses de ça?

Vous pouvez essayer une approche "optimiste": connectez-vous d'abord, puis déconnectez-vous si vous détectez une connexion mutuelle simultanée. De cette façon, vous n'auriez pas besoin de supprimer les demandes de connexion lorsque vous établissez de nouvelles connexions: lorsqu'une connexion entrante est établie, verrouillez la liste et voyez si vous avez une connexion sortante avec le même hôte. Si c'est le cas, vérifiez l'adresse de l'hôte. S'il est plus petit que le vôtre, déconnectez votre connexion sortante; sinon, déconnectez celui qui arrive. Votre hôte homologue fera le contraire, car les adresses se compareront différemment et l'une des deux connexions sera supprimée. Cette approche vous permet d'éviter de réessayer vos connexions et vous aide potentiellement à accepter plus de demandes de connexion par unité de temps.

Lorsqu'un nœud envoie une demande à un autre, il peut inclure un entier aléatoire de 64 bits. Lorsqu'un nœud reçoit une demande de connexion, s'il a déjà envoyé l'un des siens, il conserve celui avec le nombre le plus élevé et supprime les autres. Par exemple:

Temps 1: A essaie de se connecter à B, envoie le numéro 123.

Heure 2: B essaie de se connecter à A, envoie le numéro 234.

Heure 3: B reçoit la demande de A. Puisque la propre demande de B a un nombre plus élevé, elle refuse la demande de A.

Heure 4: A reçoit la demande de B. Puisque la demande de B a un nombre plus élevé, A l'accepte et abandonne sa propre demande.

Pour générer le nombre aléatoire, assurez-vous d'amorcer votre générateur de nombres aléatoires avec / dev / urandom, plutôt que d'utiliser l'amorçage par défaut de votre générateur de nombres aléatoires, qui est souvent basé sur l'heure de l'horloge murale: il y a une chance non négligeable que deux nœuds obtiendra la même graine.

Au lieu de nombres aléatoires, vous pouvez également distribuer des nombres à l'avance (c'est-à-dire simplement numéroter toutes les machines de 1 à n), ou utiliser une adresse MAC, ou une autre manière de trouver un nombre où la probabilité de collision est si petite qu'elle est ignorable.

Si je comprends bien, le problème que vous essayez d'éviter se présente comme suit:

• Le nœud 1 demande une connexion au nœud 2
• Node1 verrouille la liste des connexions
• Node2 demande une connexion au nœud 1
• Node2 verrouille la liste des connexions
• Node2 reçoit la demande de connexion de node1, la rejette car la liste est verrouillée
• Node1 reçoit une demande de connexion de node2, la rejette car la liste est verrouillée
• Aucun des deux ne se connecte les uns aux autres.

Je peux penser à deux façons différentes de gérer cela.

1. Si vous essayez de vous connecter à un nœud et qu'il rejette votre demande avec un message "liste verrouillée", attendez un nombre aléatoire de millisecondes avant de réessayer. (Le caractère aléatoire est critique. Il est beaucoup moins probable que les deux attendent exactement le même temps et répètent le même problème à l' infini .)
2. Synchronisez les horloges des deux systèmes avec un serveur de temps et envoyez un horodatage avec la demande de connexion. Si une demande de connexion provient d'un nœud auquel vous essayez actuellement de vous connecter, les deux nœuds conviennent que celui qui a essayé de se connecter en premier gagne et que l'autre connexion est fermée.