Jak mogę uniknąć rozproszonego impasu podczas wzajemnego połączenia między dwoma węzłami?

Załóżmy, że mamy dwa węzły równorzędne: pierwszy węzeł może wysłać żądanie połączenia do drugiego, ale także drugi może wysłać żądanie połączenia do pierwszego. Jak uniknąć podwójnego połączenia między dwoma węzłami? Aby rozwiązać ten problem, wystarczy wykonać sekwencyjne operacje wykonywane w celu utworzenia przychodzących lub wychodzących połączeń TCP.

Oznacza to, że każdy węzeł powinien przetwarzać sekwencyjnie każdą nową operację tworzenia połączenia, zarówno dla połączeń przychodzących, jak i wychodzących. W ten sposób, utrzymując listę połączonych węzłów, przed zaakceptowaniem nowego połączenia przychodzącego z węzła lub przed wysłaniem żądania połączenia do węzła wystarczy sprawdzić, czy ten węzeł jest już na liście.

Aby sekwencyjnie wykonywać operacje tworzenia połączeń, wystarczy wykonać blokadę na liście połączonych węzłów: w rzeczywistości dla każdego nowego połączenia do tej listy dodawany jest identyfikator nowego podłączonego węzła. Zastanawiam się jednak, czy to podejście może spowodować rozproszenie rozproszone :

• pierwszy węzeł może wysłać żądanie połączenia do drugiego;
• drugi węzeł mógłby wysłać żądanie połączenia do pierwszego;
• zakładając, że dwa żądania połączenia nie są asynchroniczne, oba węzły blokują wszelkie przychodzące żądania połączenia.

Jak mogę rozwiązać ten problem?

AKTUALIZACJA: Jednak nadal muszę blokować listę za każdym razem, gdy tworzone jest nowe (przychodzące lub wychodzące) połączenie, ponieważ inne wątki mogą uzyskiwać dostęp do tej listy, problem zakleszczenia nadal pozostaje.

AKTUALIZACJA 2: W oparciu o twoją radę napisałem algorytm zapobiegający wzajemnej akceptacji żądania logowania. Ponieważ każdy węzeł jest równorzędny, może mieć procedurę klienta do wysyłania nowych żądań połączenia oraz procedurę serwera do akceptowania połączeń przychodzących.

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
}

Przykład: Port IP: węzeł A to A: 7001 - Port IP: węzeł B to B: 8001.

Załóżmy, że węzeł A wysłał żądanie logowania do węzła B: 8001. W takim przypadku węzeł A wywołuje procedurę logowania, wysyłając, wysyłając własny adres nasłuchiwania (A: 7001). W konsekwencji tabela sąsiadów A węzła A zawiera adres zdalnego węzła (B: 8001): adres ten jest powiązany ze stanem PODŁĄCZANIE. Węzeł A czeka na zaakceptowanie lub odrzucenie żądania logowania przez węzeł B.

W międzyczasie węzeł B mógł również wysłać żądanie połączenia na adres węzła A (A: 7001), a następnie węzeł A może przetwarzać żądanie węzła B. Tak więc tabela sąsiadów B zawiera adres zdalnego węzeł (A: 7001): ten adres jest powiązany ze stanem PODŁĄCZANIE. Węzeł B czeka na węzeł A zaakceptuj lub odrzuć żądanie logowania.

Jeśli po stronie serwera węzła A odrzuca żądanie z B: 8001, to muszę się upewnić, że po stronie serwera węzła B zaakceptuje żądanie z A: 7001. Podobnie, jeśli strona serwera węzła B odrzuci żądanie od A: 7001, to muszę się upewnić, że strona serwera węzła A zaakceptuje żądanie od B: 8001.

Zgodnie z zasadą „małego adresu” w tym przypadku węzeł A odrzuci żądanie logowania przez węzeł B, podczas gdy węzeł B zaakceptuje żądanie z węzła A.

Co myślicie o tym?

Możesz wypróbować podejście „optymistyczne”: najpierw połącz, a następnie rozłącz, jeśli wykryjesz jednoczesne wzajemne połączenie. W ten sposób nie będziesz musiał powstrzymywać żądań połączenia podczas nawiązywania nowych połączeń: po ustanowieniu połączenia przychodzącego zablokuj listę i sprawdź, czy masz połączenie wychodzące z tym samym hostem. Jeśli tak, sprawdź adres hosta. Jeśli jest mniejszy od twojego, odłącz połączenie wychodzące; w przeciwnym razie odłącz przychodzący. Twój równorzędny host postąpi odwrotnie, ponieważ adresy będą się porównywać inaczej, a jedno z dwóch połączeń zostanie zerwane. Takie podejście pozwala uniknąć ponawiania połączeń i potencjalnie pomaga zaakceptować więcej żądań połączeń na jednostkę czasu.

Gdy jeden węzeł wysyła żądanie do drugiego, może zawierać losową 64-bitową liczbę całkowitą. Gdy węzeł otrzyma żądanie połączenia, jeśli już wysłał jeden ze swoich, zachowuje ten o najwyższym numerze i odrzuca pozostałe. Na przykład:

Czas 1: A próbuje połączyć się z B, wysyła numer 123.

Czas 2: B próbuje połączyć się z A, wysyła numer 234.

Czas 3: B otrzymuje żądanie A. Ponieważ własne żądanie B ma wyższą liczbę, odrzuca żądanie A.

Czas 4: A otrzymuje żądanie B. Ponieważ żądanie B ma wyższą liczbę, A przyjmuje je i odrzuca własne żądanie.

Aby wygenerować liczbę losową, upewnij się, że zaszczepiłeś generator liczb losowych za pomocą / dev / urandom, zamiast używać domyślnego inicjowania generatora liczb losowych, który często opiera się na zegarze ściennym: istnieje nieunikniona szansa, że ​​dwa węzły otrzyma to samo ziarno.

Zamiast liczb losowych można również rozdzielić liczby z wyprzedzeniem (tj. Po prostu numerować wszystkie maszyny od 1 do n) lub użyć adresu MAC lub w inny sposób znaleźć liczbę, w której prawdopodobieństwo kolizji jest tak małe, że może być niezapomniany.

Jeśli rozumiem, problem, którego próbujesz uniknąć, wygląda następująco:

• Węzeł 1 żąda połączenia z węzła 2
• Węzeł 1 blokuje listę połączeń
• Węzeł 2 żąda połączenia z węzła 1
• Node2 blokuje listę połączeń
• Węzeł2 odbiera żądanie połączenia z węzła 1, odrzuca, ponieważ lista jest zablokowana
• Węzeł 1 odbiera żądanie połączenia z węzła 2, odrzuca, ponieważ lista jest zablokowana
• Żadne z nich nie łączy się ze sobą.

Mogę wymyślić kilka różnych sposobów radzenia sobie z tym.

1. Jeśli spróbujesz połączyć się z węzłem, który odrzuci twoje żądanie z komunikatem „lista zablokowana”, odczekaj losową liczbę milisekund przed ponowną próbą. (Losowość jest krytyczna. To sprawia, że ​​znacznie mniej prawdopodobne jest, że oboje poczekają dokładnie tyle samo czasu i powtórzą ten sam problem ad infinitum .)
2. Zsynchronizuj zegary obu systemów z serwerem czasu i wyślij znacznik czasu wraz z żądaniem połączenia. Jeśli żądanie połączenia przychodzi z węzła, z którym aktualnie próbujesz się połączyć, oba węzły zgadzają się, że którykolwiek z nich próbował połączyć się pierwszy, wygrywa, a drugie połączenie zostaje zamknięte.