Harmony: The Art of Reconciliation

University Of Pennsylvania, Philadelphia PA

Investigators

Abstract

0429836 Harmony: The Art of Reconciliation Benjamin C. Pierce This project aims to build a generic tool for reconciling disconnected updates to heterogeneous, structured, replicated data -- usable, for instance, to synchronize bookmark files from different web browsers running on multiple machines. A central theme is bringing ideas from programming languages to bear on problems more commonly regarded as belonging to the purview of databases or distributed systems. In particular, a major focus concerns developing the foundations of "bi-directional programming languages," in which every program denotes a pair of functions -- one for extracting a view of some complex data structure, and another for putting back an updated view into the original structure. Similarly, the issue of alignment of information during reconciliation will be addressed by focusing on the type structure of the data being reconciled. This linguistic perspective may offer new insights into classical problems in these areas, such as the well known "view update problem" in databases. At the same time, reconciling complex abstract formats, such as ordered lists and trees, brings to fore a number of algorithmic issues concerning how to meaningfully weave together disconnected changes in replicas.