Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Suppose we have two peer nodes: the first node can send a connection request to the second one, but also the second one can send a connection request to the first one. How to avoid a double connection between the two nodes? To resolve this issue, it would be sufficient to make sequential the operations performed for creating inbound or outbound TCP connections.

This means that each node should process sequentially each new connection creation operation, both for incoming connections and for outgoing connections. In this way, maintaining a list of connected nodes, before accepting a new incoming connection from a node or before sending a connection request to a node, it will be sufficient to check if this node is already present in the list.

In order to make sequential the operations of creating connections, it is sufficient to perform a lock on the list of connected nodes: in fact, for each new connection, the identifier of the new connected node is added to this list. However, I wonder if this approach can cause distributed deadlock:

  • the first node could send a connection request to the second one;
  • the second node could send a connection request to the first one;
  • assuming that the two connection requests are not asynchronous, both nodes lock any incoming connection requests.

How could I solve this problem?

UPDATE: However, I still have to lock on the list every time a new (incoming or outgoing) connection is created, since other threads may access this list, then the problem of deadlock would still remain.

UPDATE 2: Based on your advice I wrote an algorithm to prevent mutual acceptance of a login request. Since each node is a peer, it could have a client routine to send new connection requests and a server routine to accept incoming connections.

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
}

Example: The IP:port of node A is A:7001 - The IP:port of node B is B:8001.

Suppose that the node A has sent a login request to the node B:8001. In this case, the node A calls the login routine by sending by sending its own listening address (A:7001). As a consequence, the neighbors_table of node A contains the address of the remote node (B:8001): this address is associated with the CONNECTING state. Node A is waiting for node B accept or deny the login request.

Meanwhile, the node B also may have sent a connection request to the address of node A (A:7001), then node A may be processing the request of the node B. So, the neighbors_table of node B contains the address of the remote node (A:7001): this address is associated with the CONNECTING state. Node B is waiting for node A accept or deny the login request.

If the server side of node A rejects the request from B:8001, then I must be sure that server side of node B will accept the request from A:7001. Similarly, if the server side of node B rejects the request from A:7001, then I must be sure that server side of node A will accept the request from B:8001.

According to the "small address" rule, in this case the node A will reject the login request by the node B, while node B will accept the request from node A.

What do you think about that?

share|improve this question
    
These kinds of algorithms are pretty tough to analyze and prove. However, there is a researcher who is expert in a great many aspects of distributed computing. Check out Leslie Lamport's publications page at: research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html –  DeveloperDon Aug 24 '12 at 6:28

3 Answers 3

up vote 3 down vote accepted

You can try an "optimistic" approach: connect first, then disconnect if you detect a concurrent mutual connection. This way you would not need to keep out the connection requests while you are making new connections: when an incoming connection is established, lock the list, and see if you have an outgoing connection to the same host. If you do, check host's address. If it is smaller than yours, disconnect your outgoing connection; otherwise, disconnect the incoming one. Your peer host will do the opposite, because the addresses will compare differently, and one of the two connections will be dropped. This approach lets you avoid retrying your connections, and potentially helps you to accept more connection requests per unit of time.

share|improve this answer
    
However, I still have to lock on the list every time a new (incoming or outgoing) connection is created, since other threads may access this list, then the problem of deadlock would still remain. –  enzom83 Aug 24 '12 at 0:12
    
@enzom83 No, the deadlock is not possible under this scheme, because the peer never needs to wait for you to complete the operation that requires locking. The mutex is to protect the internals of your list; once you acquire it, you leave in a known amount of time, because you do not need to wait for any other resource inside the critical section. –  dasblinkenlight Aug 24 '12 at 1:16
    
Ok, but the deadlock could occur if the connection request is not asynchronous, and if it is performed inside the critical section: in this case, the node can not leave the mutex until its connection request has been accepted. Otherwise I should perform the lock on the list only to add (or remove) a node: in this case I should check for duplicate connections, etc.. Finally, another option would be to send an asynchronous connection request. –  enzom83 Aug 24 '12 at 7:28
1  
@enzom83 As long as you do not request connections from within the critical section, you wouldn't get a distributed deadlock. That's the idea behind the optimistic approach - you perform a lock on the list only to add or remove a node, and if you find a reciprocal connection when adding a node, you break it after leaving the critical section, using the "smaller address" rule (from the answer). –  dasblinkenlight Aug 24 '12 at 12:05

When one node sends a request to another, it could include a random 64-bit integer. When a node gets a connection request, if it has already sent one of it's own, it keeps the one with the highest number and drops the others. For example:

Time 1: A tries to connect to B, sends the number 123.

Time 2: B tries to connect to A, sends the number 234.

Time 3: B receives A's request. Since B's own request has a higher number, it denies A's request.

Time 4: A receives B's request. Since B's request has a higher number, A accepts it and drops its own request.

To generate the random number, make sure you seed your random number generator with /dev/urandom, rather than using the default seeding of your random number generator, which is often based on wall clock time: there's a not-ignorable chance that two nodes will get the same seed.

Instead of random numbers, you could also distribute numbers ahead of time (i.e. just number all machines from 1 to n), or use a MAC address, or some other way of finding a number where the probability of collision is so small as to be ignorable.

share|improve this answer

If I understand, the problem you're trying to avoid goes like this:

  • Node1 requests connection from node 2
  • Node1 locks connection list
  • Node2 requests connection from node 1
  • Node2 locks connection list
  • Node2 receives connection request from node1, rejects because list is locked
  • Node1 receives connection request from node2, rejects because list is locked
  • Neither one ends up connecting to each other.

I can think of a couple different ways to deal with this.

  1. If you try to connect to a node, and it rejects your request with a "list locked" message, wait a random number of milliseconds before trying again. (The randomness is critical. It makes it much less likely that both will wait for the exact same amount of time and repeat the same problem ad infinitum.)
  2. Synchronize both systems' clocks with a time server, and send a timestamp along with the connection request. If a connection request comes in from a node that you're currently trying to connect to, then both nodes agree that whichever one tried to connect first wins, and the other connection gets closed.
share|improve this answer
    
The problem is also that the node receiving the request can not reject the connection, but it would remain in wait indefinitely to get the lock on the list. –  enzom83 Aug 23 '12 at 23:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.