Login
Computer Science @ Rochester
Monday, November 14, 2011
11:00 AM
Computer Studies Bldg. 209
Bill Bolosky
Microsoft Research
Paxos Replicated State Machines as the Basis of a High-Performance Data Store
Conventional wisdom holds that Paxos is too expensive to use for high-volume, high-throughput, data-intensive applications. Consequently, fault-tolerant storage systems typically rely on special hardware, semantics weaker than sequential consistency, a limited update interface (such as append-only), primary-backup replication schemes that serialize all reads through the primary, clock synchronization for correctness, or some combination thereof. We demonstrate that a Paxos-based replicated state machine implementing a storage service can achieve performance close to the limits of the underlying hardware while tolerating arbitrary machine restarts, some permanent machine or disk failures and a limited set of Byzantine faults. We also compare it with two versions of primary-backup. The replicated state machine can serve as the data store for a file system or storage array. We present a novel algorithm for ensuring read consistency without logging, along with a sketch of a proof of its correctness.

BIO: Bill Bolosky has been a member of Microsoft Research since 1992. He has interests in areas loosely centered around distributed systems, storage and operating systems but feels free to branch out to work on any problems that seem interesting, ranging from process priority management for IO bound processes to gene sequencing. He has published in most of the major systems conferences with regularity if not great frequency, and has even helped Microsoft ship a product or two. He's currently the PC co-chair for FAST '12.

Refreshments will be provided at 10:45AM