A structured peer-to-peer overlay performs a key-based routing (KBR) that achieves a strong routing consistency guarantee as well as reasonable scalability. The key space of the structured overlay is partitioned into zones, each separately managed by a group membership service that provides total ordering of membership query and change actions. The strongly consistent KBR has two phases: first, a key value is routed to a contact node in its zone via a weakly consistent KBR protocol; and then performing a lookup of the destination node for the key value by the contact node using the group membership service of the zone. By appropriately tuning the zone size, the strongly consistent KBR balances the trade-off between scalability and routing liveness. The KBR can maintain this balance by merging and splitting zones to account for system chum and scale changes.