A method of maintaining routing tables at nodes of an overlay network, where a routing table of a given node contains, for each of a set of neighboring successor and predecessor nodes, a mapping between an overlay network address of the node and a physical locator of the node. The method comprises, upon or immediately prior to departure of a node from the overlay network, sending a Leave request from the departing node (or one of the neighboring nodes of the departing node aware of the departure) to each neighboring node (or each other neighboring node of the departing node), indicating the departure and containing one or more mappings for nodes not contained within the routing table of the recipient node. Each neighboring node (or each other neighboring node) receives the Leave request and uses said mapping(s) to update its routing table.