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.