Probabilistic quorum systems in wireless ad hoc networks

Quorums are a basic construct in solving many fundamental distributed computing problems. One of the known ways of making quorums scalable and efficient is by weakening their intersection guarantee to being probabilistic. This paper explores several access strategies for implementing probabilistic quorums in ad hoc networks. In particular, we present the first detailed study of asymmetric probabilistic bi-quorum systems and show its advantages in ad hoc networks. The paper includes both a formal analysis of these approaches backed by a simulation based study. In particular, we show that one of the strategies, based on random walks, exhibits the smallest communication overhead.

1 Introduction

Quorums are a basic construction in many distributed systems. They can be used as building blocks (or at least as design pattern) in solving various fundamental problems such as Consensus [16], distributed dictionaries and location services [12], distributed storage [2], [25], etc. While most implementations of quorum systems are deterministic, some works have suggested the use of probabilistic quorums as a way of improving their resilience, efficiency, and scalability [27].