AF: EAGER: Data Streaming with a View towards Cloud Computing

高效处理大数据的能力正在成为现代生活的核心。越来越多的这种处理发生在“云中”，在强大服务器的大型集群上，其提供的计算能力远远超过弱客户端上可用的计算能力，例如，最终用户的个人电脑。许多大数据问题需要对几乎连续生成的海量数据流进行时空高效的处理：例如金融交易、医疗记录和科学实验数据。访问云计算服务使得许多数据流问题变得易于处理，而这些问题对于弱客户端来说是难以解决的。现有的云计算服务不能保证客户端的计算将无错误地执行。在这个项目的过程中，PI将致力于设计和研究技术的理论基础，使弱客户端能够信任在使用此类服务时获得的结果。该项目期间设计的新算法可能会对云计算和数据流系统的实践产生影响。该项目将使研究生和本科生能够在理论计算机科学研究和展示方面进行培训，并在实验中研究与这种值得信赖的云计算相关的算法思想。第一个是关于算法设计，其中PI将在上述弱客户端/强服务器设置中寻求新的或改进的算法（在空间使用和通信成本方面）。特别是，PI将重新审视这些基本问题，如范数估计和聚类。第二条线索是复杂性理论：PI将寻求理解这种计算设置的局限性，最有可能的是通过证明通信复杂性的新下限。这条线索自然会引出关于亚瑟-梅林交流的公开问题，这个话题长期以来一直很难，即使是微小的进步也可能是重大的突破。

The ability to efficiently and effectively process big data is becoming central to modern life. Increasingly, much of this processing takes place "in the cloud", on large clusters of powerful servers, which provide computational power far exceeding those available on a weak client, e.g., an end-user's personal computer. Many big data problems require time-and-space-efficient processing of massive data streams generated almost continuously: examples include financial transactions, medical records, and scientific experimentaldata. Access to a cloud computing service makes tractable a number of data streaming problems that would otherwise be intractable for a weak client.Existing cloud computing services do not give clients a guarantee that their computations will be executed error-free. In the course of this project, the PI will work to design and study the theoretical foundations of techniques that would enable a weak client to trust results arrived at when working withsuch a service. New algorithms designed during this project could have an impact on the practice of cloud computing and data streaming systems. The project will enable the training of graduate and undergraduate students in theoretical computer science research and exposition, and in experimentally studying algorithmic ideas relevant to such trustworthy cloud computing.The project has two major threads. The first is about algorithm design, wherein the PI will seek new or improved algorithms (in terms of space usage and communication costs) in the above weak-client/powerful-server setting. In particular, the PI will revisit such fundamental problems as norm estimation and clustering. The second thread is complexity-theoretic: the PI will seek to understand the limitations of this computational setting, most likely through proving new lower bounds in communication complexity. This thread naturally leads to open questions about Arthur-Merlin communication, a topic long known to be difficult enough that even small advances could be significant breakthroughs.