Computer Science Colloquium

New Systems, Algorithms, and Data Structures for High Availability

Siddhartha Sen, Princeton University

March 29, 2013 11:30AM
Warren Weaver Hall, 1302
251 Mercer Street
New York, NY 10012
(Directions)

Spring 2013 Colloquia Calendar

Host

Denis Zorin

Synopsis

Users of Internet services are increasingly intolerant of delays and outages, while demanding an increasingly rich and consistent online experience. One screenshot, and a website that is down or misbehaving spreads through the news like wildfire. Yet protecting against such failures -- whether due to misconfigurations, bugs, or even malice -- is notoriously expensive. At the same time, the pressure to increase availability pushes system designers to cut corners, sometimes with disastrous consequences.

In this talk, I will describe new systems and theory for delivering high availability to users, inspired by real-world debacles, some of which are unknown to the public. A unifying approach in my research is to integrate theoretical innovations into the final stages of system design, giving robust guarantees that are also practical. First, I will describe a system that allows any Internet service to tolerate arbitrary faults scalably on read-mostly workloads, as well as new algorithms to scale this fault tolerance to a million nodes on general workloads. Then, I will describe an indexing technique used by database systems to increase transaction concurrency, and theoretically explain why it failed for one company, leading to the design of new data structures that are being incorporated into algorithms textbooks. I will also briefly discuss my other work on high availability, such as a system for saving energy on enterprise desktops, and my ongoing work on a system for rich analysis of globally distributed, real-time data.

Bio

Siddhartha Sen is a computer science PhD candidate at Princeton University and a junior research scientist at New York University. He designs and builds distributed systems that are provably scalable and robust, by tackling theoretical questions that arise during system creation. He received his BS degrees in computer science and mathematics and his MEng degree in computer science from MIT. He spent three years at Microsoft building a network load balancer for Windows Server, holding several patents for this work. Siddhartha received the first Google Fellowship in Fault-Tolerant Computing in 2009 and the best student paper award at PODC in 2012.


top | contact webmaster