<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'>Sid Sen will present his preFPO on Thursday March 8 at 11AM in Room 402. <br>The members of his committee are: Bob Tarjan, advisor, reader; Michael Freedman, <br>advisor, reader; Jen Rexford, reader; Vivek Pai and Bob Sedgewick, nonreaders. <br>Everyone is invited to attend his talk. His abstract follows below.<br>----------------------------------<div style="color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><div>Title: New Data Structures and Algorithms for Highly-Available Distributed Systems</div><div><br></div><div>Abstract:</div><div><br></div><div><div>We design new data structures and algorithms to improve the availability of</div>
<div>distributed systems. Our work spans several settings, from individual database</div><div>servers to large-scale peer-to-peer systems. A unifying approach in our work is</div><div>to synergize theory and systems until a solution that is both practical and</div>
<div>provably good is attained.</div><div><br></div><div>In database systems, availability suffers when transactions contend for locks on</div><div>shared index structures. To increase transaction concurrency, many databases</div>
<div>such as Berkeley DB avoid rebalancing B-tree indices after deletions, only</div><div>rebalancing after insertions. But when one company tried this technique with</div><div>red-black trees, the result was an extended downtime and litigation. Using a</div>
<div>novel exponential-potential analysis, we theoretically justify why deletion</div><div>without rebalancing works in B-trees but fails in red-black trees, and devise</div><div>a new binary tree called Ravl trees that works.</div>
<div><br></div><div>In peer-to-peer systems, the availability of a service depends on unreliable</div><div>participant machines. These machines fail not just by crashing, but also in</div><div>arbitrary ways, e.g. due to bugs or malice. To scale such a system securely, we</div>
<div>must partition it into smaller groups that remain locally correct despite a</div><div>dynamic, global adversary. We expose serious practical limitations in the</div><div>current-best algorithm for this, and devise a new algorithm called Commensal</div>
<div>Cuckoo that keeps the system available two orders of magnitude longer.</div><div><br></div><div>In enterprise desktop and some server cluster settings, availability is often</div><div>desired in conjunction with energy efficiency. Unfortunately, existing</div>
<div>energy-saving solutions require special hardware or virtualization technology</div><div>that IT departments are unwilling to deploy. To address this, we built GreenUp,</div><div>a system that allows any machine to act as a proxy for other sleeping machines,</div>
<div>ensuring their availability to clients seamlessly. Notably, while optimizing</div><div>load distribution in GreenUp, we discovered and analyzed a new balls-in-bins</div><div>process with connections to population genetics and high-dimensional geometry.</div>
<div>GreenUp is deployed on over ~1,100 machines within Microsoft.</div><div><br></div><div>Though often ignored, networking is as critical to the availability of a system</div><div>as the servers themselves. Beyond connectivity, congestion in the network can</div>
<div>render services unavailable by starving traffic, even when sufficient bandwidth</div><div>exists. We address this problem in datacenter networks through LocalFlow, a flow</div><div>routing algorithm based on splitting flows. Unlike prior solutions, LocalFlow is</div>
<div>switch-local (and hence scalable) and routes optimally. Realizing LocalFlow</div><div>required a novel theoretical model as well as novel mechanisms for practical</div><div>deployment on programmable commodity switches.</div>
<div><br></div><div><br></div><br></div></div><br></div></body></html>