AitF: FULL: Collaborative Research: Optimizing Networked Systems with Limited Information

在过去的几十年里，世界上占主导地位的计算基础设施已经逐渐从个人计算机过渡到规模和复杂程度前所未有的大规模网络系统。这不仅导致了巨大的技术和工程挑战，而且还对经典算法理论中的基本假设提出了质疑。一个明显的区别是，在这种分散和不同的系统中，算法可以访问的信息有限。例如，内容交付网络为一组不同的终端设备提供服务，并且必须优化性能，而通常不知道要为其优化的设备。同样，数据中心调度器必须针对其忽略的未来需求进行优化。在这个项目中，PI试图解决在现实世界网络系统中出现的非透视性计算模型中的新算法问题。该项目的成功完成将导致在建立可靠和有弹性的信息网络方面取得新的进展。该项目将促进理论家和实践者之间的合作和思想交流，并将为几名研究生提供关于现实世界算法的广泛培训，同时注意性别多样性和代表性不足群体的参与。该项目的目标是在有限的信息环境下为联网系统设计具有可证明保证的新颖算法。特别是，PI计划解决互联网中三个主要计算基础设施模型中的关键算法问题：(A)数据中心：分配需要处理节点和集群上的多个资源的可并行作业；(B)广域集群网络：长期规划资源部署和客户端-服务器模型中的协同操作；以及(C)P2P浏览器云：网络和游戏应用程序中的内容交付，以及大量松散耦合的不可靠浏览器结构上的集群计算。这些问题领域的特点是不确定性和有限的信息，原因有几个，包括对未来预测的不确定性，网络系统中各个组件的自治性，以及网络体系结构的分布式实现。作为该项目的一部分设计的算法将在真实世界的试验台上进行评估和优化。

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.