Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
P-Grid
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
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 (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=http://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== *[http://www.manfredhauswirth.org/research/talks/P-Grid-Sbg.pdf manfredhauswirth.org] [[Category:File sharing]] [[Category:Peer-to-peer file sharing]] [[Category:Distributed data storage]]
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)
Pages transcluded onto the current version of this page
(
help
)
:
Template:Citation needed
(
edit
)
Template:Cite book
(
edit
)
Template:Cite conference
(
edit
)
Template:Cite journal
(
edit
)
Template:Reflist
(
edit
)