Patent ID: 7673069

Claim:
A method of enforcing routing consistency among peer computing device nodes on a network organized in structured peer-to-peer overlays, the method comprising: partitioning a key space of a structured peer-to-peer overlay having a plurality of computing device nodes into a plurality of zones, wherein at least one of the zones encompasses keys of more than one of said computing device nodes; providing a group membership service by one of said computing device nodes per zone to manage computing device nodes of their respective zones; performing key-based routing within the structured peer-to-peer overlay by: performing routing of a key value via a weakly consistent key-based routing to a contact computing device node in the zone to which the key value belongs; and determining by the contact computing device node using the group membership service of the zone with a strong consistency guarantee a target computing device node to which the key value belongs in the zone, wherein said strong consistency guarantee is that determinations of which computing device node that a given key value belongs by any two computing device nodes in the zone using the group membership service yields a same result for a given version number of the zone, wherein the group membership service provides total ordering of membership queries and membership changes, and wherein the group membership service increments the version number of the zone with each membership change to the zone.