TY - GEN
T1 - Spontaneous, self-sampling quorum systems for ad hoc networks
AU - Konwar, Kishori M.
AU - Musial, Peter M.
AU - Shvartsman, Alexander A.
N1 - DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.
PY - 2008
Y1 - 2008
N2 - Quorum systems-collections of sets with pairwise nonempty intersections-are used in distributed settings to implement services such as consensus and consistent memory. Quorums have been substantially studied in static settings, however the design and analysis of quorum-based distributed services in resource-limited ad hoc networks is a relatively unexplored area. The pioneering work of Chockler, Gilbert, and Patt-Shamir [8] considers such networks and proposes an implementation of probabilistic quorum systems with per-node communication bit complexity of O (log2 n), where n is the number of nodes. The authors assumes a priori knowledge of node failure probability p, where 0 ≤ p < 1/4. Additionally their work overlooks the cost of gathering responses from quorum members by the client. We present a new probabilistic quorum construction with a lower, per quorum access, communication bit complexity of O (logn) for multi-hop networks. Our quorum access algorithm is based on self-sampling by the nodes themselves, in a way equivalent to accessing a quorum set, with high probability. In addition, we provide a novel on-line algorithm to estimate the node failure probability parameter p, thus removing the assumption that it is known a priori. This is accomplished with per node communication bit complexity of O (log2 n). We demonstrate the utility of our construction by presenting a single-writer, multi-reader algorithm that uses our probabilistic quorums to implement atomic objects in ad hoc networks, where consistency is guaranteed with high probability. We include simulation results illustrating the high probability guarantee for our atomic memory service.
AB - Quorum systems-collections of sets with pairwise nonempty intersections-are used in distributed settings to implement services such as consensus and consistent memory. Quorums have been substantially studied in static settings, however the design and analysis of quorum-based distributed services in resource-limited ad hoc networks is a relatively unexplored area. The pioneering work of Chockler, Gilbert, and Patt-Shamir [8] considers such networks and proposes an implementation of probabilistic quorum systems with per-node communication bit complexity of O (log2 n), where n is the number of nodes. The authors assumes a priori knowledge of node failure probability p, where 0 ≤ p < 1/4. Additionally their work overlooks the cost of gathering responses from quorum members by the client. We present a new probabilistic quorum construction with a lower, per quorum access, communication bit complexity of O (logn) for multi-hop networks. Our quorum access algorithm is based on self-sampling by the nodes themselves, in a way equivalent to accessing a quorum set, with high probability. In addition, we provide a novel on-line algorithm to estimate the node failure probability parameter p, thus removing the assumption that it is known a priori. This is accomplished with per node communication bit complexity of O (log2 n). We demonstrate the utility of our construction by presenting a single-writer, multi-reader algorithm that uses our probabilistic quorums to implement atomic objects in ad hoc networks, where consistency is guaranteed with high probability. We include simulation results illustrating the high probability guarantee for our atomic memory service.
KW - Ad hoc networks
KW - Probabilistic quorum system
KW - Single-writer and multi-reader
KW - Submartingale bound
UR - http://www.scopus.com/inward/record.url?scp=60349095016&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=60349095016&partnerID=8YFLogxK
U2 - 10.1109/ISPDC.2008.61
DO - 10.1109/ISPDC.2008.61
M3 - Conference contribution
AN - SCOPUS:60349095016
SN - 9780769534725
T3 - Proceedings of the 7th International Symposium on Parallel and Distributed Computing, ISPDC 2008
SP - 367
EP - 374
BT - Proceedings of the 7th International Symposium on Parallel and Distributed Computing, ISPDC 2008
T2 - 7th International Symposium on Parallel and Distributed Computing, ISPDC 2008
Y2 - 1 July 2008 through 5 July 2008
ER -