A method of maintaining routing tables at nodes of a Chord Distributed Hash Table, DHT, based overlay network, where a routing table of a given node contains, for each of a set of neighbouring successor and predecessor nodes, a mapping between an overlay network address of the node and a physical locator of the node, the method comprising: periodically exchanging DHT maintenance messages between nodes of the overlay network to allow nodes to learn of other nodes that have newly joined the network; characterised by the steps of upon departure of a node from the overlay network, sending a Leave request from one of the neighbouring nodes of the departed node that is first aware of the departure, to other neighbouring nodes of the departed node, the request indicating the departure and containing either at least one mapping for at least one node not contained within the routing table of the recipient node or no mappings; and receiving a Leave request at said each other neighbouring node and using said at least one mapping to update the routing table at the recipient node; wherein the neighbouring node that is first aware of the departure performs the following steps of: estimating the routing table of the departed node; for each of the other neighbouring nodes, estimating the routing table of said each other neighbouring node based on the estimated routing table of the departed node; and including said at least one mapping or no mappings based on the estimated routing table of said each other neighbouring node into the Leave request sent to said each other neighbouring node. periodically exchanging DHT maintenance messages between nodes of the overlay network to allow nodes to learn of other nodes that have newly joined the network; characterised by the steps of upon departure of a node from the overlay network, sending a Leave request from one of the neighbouring nodes of the departed node that is first aware of the departure, to other neighbouring nodes of the departed node, the request indicating the departure and containing either at least one mapping for at least one node not contained within the routing table of the recipient node or no mappings; and receiving a Leave request at said each other neighbouring node and using said at least one mapping to update the routing table at the recipient node; wherein the neighbouring node that is first aware of the departure performs the following steps of: estimating the routing table of the departed node; for each of the other neighbouring nodes, estimating the routing table of said each other neighbouring node based on the estimated routing table of the departed node; and including said at least one mapping or no mappings based on the estimated routing table of said each other neighbouring node into the Leave request sent to said each other neighbouring node. estimating the routing table of the departed node; for each of the other neighbouring nodes, estimating the routing table of said each other neighbouring node based on the estimated routing table of the departed node; and including said at least one mapping or no mappings based on the estimated routing table of said each other neighbouring node into the Leave request sent to said each other neighbouring node. estimating the routing table of said each other neighbouring node based on the estimated routing table of the departed node; and including said at least one mapping or no mappings based on the estimated routing table of said each other neighbouring node into the Leave request sent to said each other neighbouring node.