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.