Editing P-Grid (section)

== Overview ==
[[Image:PGrid.jpg|400px|thumb|For the sake of simplicity, this figure does not show replication.]]

P-Grid abstracts a [[trie]] and resolves queries based on prefix matching. The actual topology has no hierarchy. Queries are resolved by matching prefixes. This also determines the choice of routing table entries. Each peer, for each level of the trie, maintains autonomously routing entries chosen randomly from the complementary sub-trees.<ref name="Ray">{{cite book |last1=Ray |first1=Chhanda |title=Distributed Database Systems |date=2009 |publisher=Pearson Education India |pages=87–121}}</ref> In fact, multiple entries are maintained for each level at each peer to provide fault-tolerance (as well as potentially for query-load management). For diverse reasons including fault-tolerance and load-balancing, multiple peers are responsible for each leaf node in the P-Grid tree. These are called replicas. The replica peers maintain an independent replica sub-network and uses gossip based communication to keep the replica group up-to-date.<ref name="Jepsen">{{cite book |last1=Jepsen |first1=Thomas |title=Distributed Storage Networks: Architecture, Protocols and Management |date=2013 |publisher=John Wiley & Sons |pages=37–79}}</ref> The redundancy in both the replication of key-space partitions as well as the routing network together is called structural replication. The figure above shows how a query is resolved by forwarding it based on prefix matching.{{citation needed|date=July 2013}}