Over the past decades, the world's dominant computational infrastructure has gradually transitioned from individual personal computers to massive networked systems of unprecedented scale and complexity. Not only has this led to tremendous technological and engineering challenges, but it has also called into question fundamental assumptions in classical algorithmic theory. A defining distinction is the limited information that algorithms in such decentralized and heterogeneous systems have access to. For example, a content delivery network serves a heterogeneous set of end devices, and has to optimize performance often without knowledge of the device it is optimizing for. Similarly, a data center scheduler must be optimized for future demands that it is oblivious to. In this project, the PIs seek to address novel algorithmic questions in non-clairvoyant models of computation that arise in real world networked systems. The successful completion of this project will lead to new advances in building reliable and resilient information networks. The project will enable collaborations and exchange of ideas between theoreticians and practitioners, and will provide extensive training in real world algorithms to several graduate students, with attention paid to gender diversity and participation of under-represented groups.
The goal of the project is to design novel algorithms with provable guarantees for networked systems in limited information settings. In particular, the PIs plan to address key algorithmic problems in the three dominant computational infrastructure models in the Internet: (a) data centers: allocating parallelizable jobs requiring multiple resources on processing nodes and clusters; (b) wide-area network of clusters: long-term planning of resource deployment and synergistic operations in the client-server model; and (c) P2P browser clouds: content delivery in web and gaming applications and swarm computing on a fabric of a large number of loosely coupled unreliable browsers. These problem domains are characterized by uncertainty and limited information for several reasons, including uncertainty about future predictions, autonomy of individual components in the networked system, and distributed implementation of the network architecture. The algorithms designed as part of this project will be evaluated on and optimized for real world testbeds.
