Scalability is crucial for cloud computing to be widely adopted. Failure to scale has resulted in the demise of the social networking giant MySpace, the inability to support a user load greater than 10% of system capacity, a $4.5 billion annual power expenditure on data centers and a lack of any sophisticated measurement and monitoring systems in the cloud. The size of a cloud, which often consists of tens of thousands of machines, compels the use of low-complexity algorithms, which, when naively designed, cause significant performance degradation as the system grows large. Existing algorithms are often designed for exact, optimal solutions for smaller in-house systems and do not scale due to their centralized high-complexity nature.
This research overcomes the limitation of existing work by designing a suite of low-complexity algorithms for web services, data management, and measurement and monitoring in the cloud, which are exactly optimal only as the system size grows to infinity, but very close to optimal in finite and large systems. The algorithms are designed to address the challenges with dynamic scaling, multi-tenancy and data-intensiveness in the cloud, and for different application workloads including search, social networks and map-reduce. The research draws upon and contributes to the fields of graphical models and randomized algorithms, both of which exchange sparse information locally to achieve complex global objectives in large systems. The project also includes significant outreach programs in the form of workshops and lab open-houses, to promote undergraduate research, and the participation of women and under-represented minorities.
