View source for P-Grid

In [[distributed data store|distributed data storage]], a '''P-Grid''' is a self-organizing structured [[peer-to-peer]] system, which can accommodate arbitrary key distributions (and hence support lexicographic key ordering and range queries), still providing storage [[Load balancing (computing)|load-balancing]] and efficient search by using randomized routing.

== Salient features ==

* Good storage load-balancing despite arbitrary load-distribution over the key-space.<ref name="Antonopoulos">{{cite book |last1=Antonopoulos |first1=Nick |title=Handbook of Research on P2P and Grid Systems for Service-Oriented Computing: Models, Methodologies and Applications: Models, Methodologies and Applications |date=2010 |publisher=IGI Global |pages=323–892}}</ref>
* Range queries can be naturally supported and efficiently processed on P-Grid because P-Grid abstracts a trie-structure, and supports (rather) arbitrary distribution of keys, as observed in realistic scenarios.<ref name="Antonopoulos" />
* A Self-referential directory is realized to provide peer identity persistence over multiple sessions.<ref name="Antonopoulos" />
* A gossip primitive based update mechanism for keeping replicated content up-to-date.<ref name="Antonopoulos" />
* Easy merger of multiple P-Grids, and hence decentralized bootstrapping of the P-Grid network.<ref name="Antonopoulos" />
* Query-adaptive caching is easy to realize on P-Grid to provide query load-balancing where peers have restricted capacity.<ref name="Antonopoulos" />

== 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|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}}

== Range queries in P-Grid ==

P-Grid partitions the key-space in a granularity adaptive to the load at that part of the key-space. Consequently, its possible to realize a P-Grid [[overlay network]] where each peer has similar storage load even for non-uniform load distributions. This network probably provides as efficient search of keys as traditional [[distributed hash table]]s (DHTs) do. Note that in contrast to P-Grid, DHTs work efficiently only for uniform load-distributions.<ref name="Pitoura">{{cite conference |last1=Pitoura|first1=Pitoura |last2=Ntarmos|first2=Nikos |last3=Triantafillou|first3=Peter |title=Replication, load balancing and efficient range query processing in DHTs |conference=International Conference on Extending Database Technology |date=2006 |pages=131–148|doi=10.1007/11687238_11}}</ref>

Hence we can use a lexicographic order preserving function to generate the keys, and still realize a load-balanced P-Grid network which supports efficient search of exact keys. Moreover, because of the preservation of lexicographic ordering, range queries can be done efficiently and precisely on P-Grid. The trie-structure of P-Grid allows different range query strategies, processed serially or in parallel, trading off message overheads and query resolution latency.<ref name="Datta">{{cite conference |title=Range queries in trie-structured overlays |conference=Fifth IEEE International Conference on Peer-to-Peer Computing |date=2005 |pages=57–66|doi=10.1109/P2P.2005.31|last1=Datta |first1=A. |last2=Hauswirth |first2=M. |last3=John |first3=R. |last4=Schmidt |first4=R. |last5=Aberer |first5=K. |isbn=0-7695-2376-5 |url=https://infoscience.epfl.ch/record/54360 }}</ref> Simple vector-based data storage architectural frameworks are also subject to variable query limitations within the P-Grid environment.<ref name="Oliker">{{cite journal |doi=10.1177/1094342006085020|title=Scientific Application Performance on Leading Scalar and Vector Supercomputering Platforms|journal=The International Journal of High Performance Computing Applications|volume=22|pages=5–20|year=2008|last1=Oliker|first1=Leonid|last2=Canning|first2=Andrew|last3=Carter|first3=Jonathan|last4=Shalf|first4=John|last5=Ethier|first5=Stéphane|s2cid=5347699}}</ref>

==References==
{{reflist}}

==External links==
*[https://www.manfredhauswirth.org/research/talks/P-Grid-Sbg.pdf manfredhauswirth.org]

[[Category:File sharing]]
[[Category:Peer-to-peer file sharing]]
[[Category:Distributed data storage]]