When and How to Change Quorums on Wide Area Networks

In wide-area settings, unpredictable events, such as flash crowds caused by nearly instantaneous popularity of services, can cause servers that are expected to respond quickly to instead suddenly respond slowly. This presents a problem for achieving consistently good performance in quorum-based distributed systems, in which clients must choose which quorums (sets of servers) to access. Typically, clients are motivated to choose quorums containing the servers that respond fastest. Often, these may be the closest servers, but when the closest servers are particularly slow to respond, e.g., because of a changed workload, servers that are farther may actually respond faster. In this paper, we show how clients can locally change their quorum selections efficiently such that the overall system performance rapidly converges to that of the best global strategy for the current conditions. Moreover, we discuss how to benefit even when changes in quorums must be accompanied by expensive state-transfer operations.