Meeting the challenges of massive networks and systems

Massive systems and networks have become ubiquitous. While there is a remarkable amount of work on analyzing and designing algorithms for smaller systems, the vast majority of it simply does not scale: an algorithm that takes seconds to run on a system with thousands of nodes might take weeks on a system with billions. New ideas are required if we hope to have the same success with massive systems as we do with smaller ones. The field of Local computation algorithms (LCAs), which I founded together with Ronitt Rubinfeld, Gil Tamir and Ning Xie, provides a rigorous framework for solving problems on huge systems. I will present one technique for designing LCAs: a reduction to online algorithms, and show how it can be used to design fast and robust distributed solvers for linear and convex programs. I will also describe how we can use insights from this technique to design approximate