A quorum lease is a new technique that allows Paxos-based systems to perform reads with high throughput and low latency. Quorum leases do not sacrifice consistency and have only a small impact on system availability and write latency. Quorum leases allow a majority of replicas to perform strongly consistent local reads, which substantially reduces read latency at those replicas (e.g., by two orders of magnitude in wide-area scenarios). Previous techniques for performing local reads in Paxos systems either (a) sacrifice consistency; (b) allow only one replica to read locally; or (c) decrease the availability of the system and increase the latency of all updates by requiring all replicas to be notified synchronously.
Egalitarian Paxos (or EPaxos) is a new replication protocol based on Paxos. EPaxos has no leader replica: clients can choose any replica to submit a command to, and concurrent commands are committed simultaneously without causing the "dueling leaders" problem of classic Paxos. As a result EPaxos achieves optimal wide-area commit latency for the most common deployments of quorum-based replication (three and five replicas respectively) and high throughput due to perfect load-balancing. Furthermore, EPaxos has higher performance stability than previous protocols when replicas are slow or crash.
I presented EPaxos at SOSP 2013.
Taking the fullest advantage of the low latency and high bandwidths of emerging memories such as phase change memory (PCM), spin torque, and Memristor necessitates a serious look at placing these persistent storage technologies on the main memory bus. Doing so, however, introduces critical challenges of not sacrificing the data reliability and consistency that users demand from storage. We introduce techniques for (1) robust wear-aware memory allocation, (2) preventing of erroneous writes, and (3) consistency-preserving updates that are cache-efficient.
These articles present a new, memory efficient and cache-optimized algorithm for simultaneously searching for a large number of patterns in a very large corpus. This algorithm builds upon the Rabin-Karp string search algorithm and incorporates a new type of Bloom filter that we call a feed-forward Bloom filter. While it retains the asymptotic time complexity of previous multiple pattern matching algorithms, we show that this technique, along with a CPU architecture aware design of the Bloom filter, can provide speedups between 2x and 30x, and memory consumption reductions as large as 50x when compared with grep. Our algorithm is also well suited for implementations on GPUs: a GPU can search for 3 million patterns at a rate of 580 MB/s, and for 100 million patterns (a prohibitive number for traditional algorithms) at a rate of 170 MB/s.
The NSDI paper applies feed-forward Bloom filters to virus scanning.