Wie kann ich einen verteilten Deadlock während einer gegenseitigen Verbindung zwischen zwei Knoten vermeiden?

Angenommen, wir haben zwei Peer-Knoten: Der erste Knoten kann eine Verbindungsanforderung an den zweiten senden, aber auch der zweite Knoten kann eine Verbindungsanforderung an den ersten senden. Wie vermeide ich eine doppelte Verbindung zwischen den beiden Knoten? Um dieses Problem zu beheben, ist es ausreichend, die zum Erstellen eingehender oder ausgehender TCP-Verbindungen ausgeführten Vorgänge nacheinander auszuführen.

Dies bedeutet, dass jeder Knoten nacheinander jede neue Verbindungserstellungsoperation verarbeiten sollte, sowohl für eingehende als auch für ausgehende Verbindungen. Auf diese Weise reicht es aus, eine Liste der verbundenen Knoten zu führen, bevor eine neue eingehende Verbindung von einem Knoten akzeptiert oder eine Verbindungsanforderung an einen Knoten gesendet wird, um zu überprüfen, ob dieser Knoten bereits in der Liste vorhanden ist.

Um die Vorgänge zum Erstellen von Verbindungen sequentiell durchzuführen, ist es ausreichend, die Liste der verbundenen Knoten zu sperren : Tatsächlich wird für jede neue Verbindung die Kennung des neuen verbundenen Knotens zu dieser Liste hinzugefügt. Ich frage mich jedoch, ob dieser Ansatz zu einem verteilten Deadlock führen kann :

• Der erste Knoten könnte eine Verbindungsanforderung an den zweiten senden.
• Der zweite Knoten könnte eine Verbindungsanforderung an den ersten senden.
• Unter der Annahme, dass die beiden Verbindungsanforderungen nicht asynchron sind, sperren beide Knoten alle eingehenden Verbindungsanforderungen.

Wie könnte ich dieses Problem lösen?

UPDATE: Ich muss die Liste jedoch immer noch jedes Mal sperren, wenn eine neue (eingehende oder ausgehende) Verbindung erstellt wird. Da andere Threads möglicherweise auf diese Liste zugreifen, bleibt das Problem des Deadlocks weiterhin bestehen.

UPDATE 2: Basierend auf Ihrem Rat habe ich einen Algorithmus geschrieben, um die gegenseitige Annahme einer Anmeldeanforderung zu verhindern. Da jeder Knoten ein Peer ist, kann er eine Client-Routine zum Senden neuer Verbindungsanforderungen und eine Server-Routine zum Akzeptieren eingehender Verbindungen haben.

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
}

Beispiel: Der IP: -Port von Knoten A ist A: 7001 - Der IP: -Port von Knoten B ist B: 8001.

Angenommen, der Knoten A hat eine Anmeldeanforderung an den Knoten B: 8001 gesendet. In diesem Fall ruft der Knoten A die Anmelderoutine auf, indem er sendet, indem er seine eigene Abhöradresse sendet (A: 7001). Infolgedessen enthält die Nachbarn-Tabelle von Knoten A die Adresse des entfernten Knotens (B: 8001): Diese Adresse ist dem Status CONNECTING zugeordnet. Knoten A wartet darauf, dass Knoten B die Anmeldeanforderung akzeptiert oder ablehnt.

In der Zwischenzeit kann der Knoten B auch eine Verbindungsanforderung an die Adresse von Knoten A (A: 7001) gesendet haben, dann kann Knoten A die Anforderung des Knotens B verarbeiten. Die Nachbarn-Tabelle von Knoten B enthält also die Adresse der Fernbedienung Knoten (A: 7001): Diese Adresse ist dem Status CONNECTING zugeordnet. Knoten B wartet darauf, dass Knoten A die Anmeldeanforderung akzeptiert oder ablehnt.

Wenn die Serverseite von Knoten A die Anforderung von B: 8001 ablehnt, muss ich sicher sein, dass die Serverseite von Knoten B die Anforderung von A: 7001 akzeptiert. Wenn die Serverseite von Knoten B die Anforderung von A: 7001 ablehnt, muss ich ebenfalls sicher sein, dass die Serverseite von Knoten A die Anforderung von B: 8001 akzeptiert.

Gemäß der Regel "kleine Adresse" lehnt in diesem Fall der Knoten A die Anmeldeanforderung durch den Knoten B ab, während der Knoten B die Anforderung von Knoten A akzeptiert.

Was denkst du darüber?

Sie können einen "optimistischen" Ansatz ausprobieren: Stellen Sie zuerst eine Verbindung her und trennen Sie dann die Verbindung, wenn Sie eine gleichzeitige gegenseitige Verbindung feststellen. Auf diese Weise müssen Sie die Verbindungsanforderungen nicht fernhalten, während Sie neue Verbindungen herstellen: Wenn eine eingehende Verbindung hergestellt wird, sperren Sie die Liste und prüfen Sie, ob Sie eine ausgehende Verbindung zu demselben Host haben. Wenn Sie dies tun, überprüfen Sie die Adresse des Hosts. Wenn es kleiner als deins ist, trennen Sie Ihre ausgehende Verbindung. Andernfalls trennen Sie den eingehenden. Ihr Peer-Host wird das Gegenteil tun, da die Adressen unterschiedlich verglichen werden und eine der beiden Verbindungen unterbrochen wird. Mit diesem Ansatz können Sie vermeiden, dass Ihre Verbindungen erneut versucht werden, und möglicherweise mehr Verbindungsanforderungen pro Zeiteinheit akzeptieren.

Wenn ein Knoten eine Anforderung an einen anderen sendet, kann er eine zufällige 64-Bit-Ganzzahl enthalten. Wenn ein Knoten eine Verbindungsanforderung erhält und bereits eine eigene gesendet hat, behält er die mit der höchsten Nummer bei und löscht die anderen. Beispielsweise:

Zeit 1: A versucht eine Verbindung zu B herzustellen und sendet die Nummer 123.

Zeit 2: B versucht, eine Verbindung zu A herzustellen, sendet die Nummer 234.

Zeit 3: B empfängt die Anfrage von A. Da die eigene Anfrage von B eine höhere Nummer hat, lehnt sie die Anfrage von A ab.

Zeit 4: A empfängt die Anfrage von B. Da die Anfrage von B eine höhere Nummer hat, akzeptiert A sie und lässt seine eigene Anfrage fallen.

Um die Zufallszahl zu generieren, stellen Sie sicher, dass Sie Ihren Zufallszahlengenerator mit / dev / urandom setzen, anstatt das Standard-Seeding Ihres Zufallszahlengenerators zu verwenden, das häufig auf der Wanduhrzeit basiert: Es besteht eine nicht zu ignorierende Chance, dass zwei Knoten vorhanden sind wird den gleichen Samen bekommen.

Anstelle von Zufallszahlen können Sie auch Zahlen im Voraus verteilen (dh nur alle Maschinen von 1 bis n nummerieren) oder eine MAC-Adresse oder eine andere Methode verwenden, um eine Zahl zu finden, bei der die Wahrscheinlichkeit einer Kollision so gering ist ignorierbar.

Wenn ich verstehe, sieht das Problem, das Sie vermeiden möchten, folgendermaßen aus:

• Knoten 1 fordert eine Verbindung von Knoten 2 an
• Knoten1 sperrt die Verbindungsliste
• Knoten 2 fordert eine Verbindung von Knoten 1 an
• Node2 sperrt die Verbindungsliste
• Knoten2 empfängt eine Verbindungsanforderung von Knoten1 und lehnt ab, da die Liste gesperrt ist
• Knoten1 empfängt eine Verbindungsanforderung von Knoten2 und lehnt ab, da die Liste gesperrt ist
• Keiner von beiden verbindet sich miteinander.

Ich kann mir ein paar verschiedene Möglichkeiten vorstellen, um damit umzugehen.

1. Wenn Sie versuchen, eine Verbindung zu einem Knoten herzustellen, und Ihre Anfrage mit der Meldung "Liste gesperrt" abgelehnt wird, warten Sie eine zufällige Anzahl von Millisekunden, bevor Sie es erneut versuchen. (Die Zufälligkeit ist kritisch. Es ist viel weniger wahrscheinlich, dass beide genau die gleiche Zeit warten und das gleiche Problem unendlich oft wiederholen .)
2. Synchronisieren Sie die Uhren beider Systeme mit einem Zeitserver und senden Sie einen Zeitstempel zusammen mit der Verbindungsanforderung. Wenn eine Verbindungsanforderung von einem Knoten eingeht, zu dem Sie gerade eine Verbindung herstellen möchten, stimmen beide Knoten darin überein, dass derjenige, der zuerst versucht hat, eine Verbindung herzustellen, gewinnt und die andere Verbindung geschlossen wird.