Guaranteeing Correctness of Lock-free Range Queries over P2P Data
|Title||Guaranteeing Correctness of Lock-free Range Queries over P2P Data|
|Publication Type||Conference Paper|
|Year of Publication||2005|
|Authors||Patterson, S, Agrawal D, El Abbadi A|
|Conference Name||The Third International Workshop on Databases, Information Systems and Peer-to-Peer Computing|
As P2P systems evolve into a platform for full-ﬂedged distributed database management systems, the need arises for sophisticated query support and guarantees on query correctness. While there has been recent work addressing range queries in P2P systems, the work on query correctness is just beginning. Linga et al. provided the ﬁrst formal deﬁnition of correctness for range queries in P2P systems and described a lock-based range query technique that is provably correct. A natural question that arises is whether it is possible to develop a lock-free protocol that can meet the same guarantee of correctness. In this paper, we demonstrate the feasibility of lock-free correct protocols by ﬁrst developing a simple, proof-of-concept query protocol and verifying that this protocol meets the correctness conditions. We then describe a more robust extended protocol and prove that for stable systems with only item insertions, item deletions, and item redistributions, this extension insures that every range query can be satisﬁed correctly.