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.