Iulian Moraru

Research and Publications


Paxos Quorum Leases

Paxos Quorum Leases: Fast Reads Without Sacrificing Writes
Iulian Moraru, David G. Andersen, Michael Kaminsky.
Awarded Best Paper. In Proceedings of the 5th ACM Symposium on Cloud Computing (SOCC'14), Seattle, Washington, USA, November 3-5, 2014.

PDF

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 (EPaxos)

There Is More Consensus in Egalitarian Parliaments
Iulian Moraru, David G. Andersen, Michael Kaminsky.
In Proceedings of the 24th ACM Symposium on Operating Systems Principles (SOSP'13), Farmington Pennsylvania, USA, November 3-6, 2013.

PDF

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.

Formal proof of correctness and (model-checkable) TLA+ specification.

Code

Slides

OS Support for Non-Volatile Main Memory

Consistent, Durable, and Safe Memory Management for Byte-addressable Non Volatile Main Memory
Iulian Moraru, David G. Andersen, Michael Kaminsky, Niraj Tolia, Nathan Binkert, Parthasarathy Ranganathan.
In Proceedings of the ACM Conference on Timely Results in Operating Systems (TRIOS), Farmington Pennsylvania, USA, November 3, 2013.

PDF

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.

Code

Feed-Forward Bloom Filters

Exact Pattern Matching with Feed-Forward Bloom Filters
Iulian Moraru, David G. Andersen.
In Proceedings of the 13th Workshop on Algorithm Engineering and Experiments (ALENEX'11), San Francisco, CA, USA, January 2011.

PDF

Also in ACM Journal of Experimental Algorithmics 17 (JEA), 2011.

SplitScreen: Enabling Efficient, Distributed Malware Detection.
Sang Kil Cha, Iulian Moraru, Jiyong Jang, John Truelove, David Brumley, David G. Andersen.
In Proceedings of the 7th USENIX USENIX Symposium on Networked Systems Design and Implementation (NSDI'10), San Jose, CA, USA, April 28-30, 2010.

PDF

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.

Code

Other

FAWNdamentally Power-Efficient Clusters
Vijay Vasudevan, Jason Franklin, David Andersen, Amar Phanishayee, Lawrence Tan, Michael Kaminsky, Iulian Moraru.
In Proceedings of HotOS XII, Monte Verita, Switzerland, May 2009.

PDF