Patent ID: 7664107

Claim:
A method for a node of a structured peer-to-peer overlay system to maintain a routing table containing a leafset group of logical neighboring nodes within the overlay system whereby the overlay system self-stabilizes toward a correct topology, the method comprising: at ping intervals, transmitting a liveness check message by said node to the logical neighboring nodes of said node's leafset group; and on receiving a liveness check message from a ping-sender node, producing a view of leafset group nodes for the ping-sender node based on nodes in at least a portion of the routing table of said node; transmitting a liveness check response by said node to the ping-sender node, the liveness check response containing information of the view of leafset group nodes for the ping-sender node; maintaining by said node information of an acquaintance set of nodes from which said node has received a liveness check message or response, and a candidate set of nodes that includes the acquaintance set and nodes identified in liveness check responses received from other nodes, wherein the leafset group of nodes for said node is a number of immediately neighboring nodes to said node from the acquaintance set; on said node receiving a liveness check response from a pong-sender node containing information identifying other nodes of the overlay system, adding the pong-sender node to the acquaintance set; and updating the candidate set of nodes to include the other nodes identified in the liveness check response; and searching by said node the candidate set of nodes for any nodes logically closer to said node than nodes currently in the leafset group of said node, and if so also transmitting the liveness check message by said node to the node logically closer than nodes currently in the leafset group.