AF: Small: Data Synchronization : Theory, Algorithms, and Practice

该项目解决了大规模、多方分布式系统对改进同步方法日益增长的需求。当用户将信息迁移到云存储时，云提供商可能会使用多个松散一致的副本，因为始终保持副本同步的开销。此外，当笔记本电脑、平板电脑或其他设备与云存储断开连接时，用户自己可能会在笔记本电脑、平板电脑或其他设备上创建松散同步的副本。在这样的设置中，定期同步或协调成为一种要求。协调在两个连接的用户的特定设置中得到了最多的研究，每个用户都包含一组密钥，而且两者都希望集合的并集。这些协议的成本通常是根据两个集合之间的对称集合差异的大小来计算的。主要调查者(PI)将专注于将协调方法推广到多方通过图表示的网络进行通信的环境。新框架的目标是涵盖谣言传播和网络编码等标准问题，以及通过编辑距离等其他度量推广到其他对象(如序列)。PI将追求的主要理论和实践挑战是开发方案，其中对象同步所需的通信量仅取决于需要同步的对象之间的差异的大小，而不是对象本身的大小。例如，对于大型数据库，同步成本应该取决于数据库之间的增量，这通常比数据库本身小得多。另一个目标是该框架将对现代基于云的部署产生实际影响，特别是大型大数据系统。由于协调的目标既包括算法效率也包括通信效率，PI将致力于在这项工作中将理论计算机科学和信息理论社区的想法结合在一起。为这些问题开发的新算法和数据结构预计也将对其他问题具有重要的额外用途。

This project addresses the growing need for improved synchronization methods for large-scale, multi-party distributed systems.  As users migrate information to cloud storage, cloud providers may use multiple loosely consistent replicas because of the overhead of keeping replicas synchronized at all times.  Further, users themselves may create loosely synchronized replicas on laptops, tablets, or other devices when they are disconnected from the cloud storage.  Periodic synchronization, or reconciliation, becomes a requirement in such settings.Reconciliation has been most studied in the specific setting of two connected users, each containing a set of keys, and both desiring the union of the sets.  The costs of these protocols is typically in terms of the size of the symmetric set difference between the two sets.  The Principal Investigator (PI) will focus on generalizing reconciliation methods to settings where many parties communicate over a network represented by a graph.  The new framework will aim to encompass standard problems such as rumor spreading and network coding, as well as generalize to other objects such as sequences with other measures such as edit distance. The primary theoretical and practical challenge the PI will pursue is to develop schemes where the amount of communication necessary for object synchronization depends only on the size of the difference among objects that need to be synchronized, and not the sizes of the objects themselves.  For example, for large databases, the synchronization cost should depend on the delta between the databases, which will generally be much smaller than the databases themselves.  A further goal is that the framework will have practical consequences for modern cloud-based deployments, especially large-scale big data systems. Because the goals of reconciliation include both algorithmic efficiency as well as communication efficiency, the PI will work to bring ideas from both the theoretical computer science and information theory communities together in this work.  The new algorithms and data structures developed for these problems are expected to have significant additional uses for other problems as well.