Harmony: The Art of Reconciliation

点击翻译按钮获取中文摘要

0429836Harmony: The Art of ReconciliationBenjamin C. PierceThis project aims to build a generic tool for reconciling disconnectedupdates to heterogeneous, structured, replicated data -- usable, forinstance, to synchronize bookmark files from different web browsersrunning on multiple machines.A central theme is bringing ideas from programming languages to bear onproblems more commonly regarded as belonging to the purview of databasesor distributed systems. In particular, a major focus concernsdeveloping the foundations of "bi-directional programming languages," inwhich every program denotes a pair of functions -- one for extracting aview of some complex data structure, and another for putting back anupdated view into the original structure. Similarly, the issue ofalignment of information during reconciliation will be addressed byfocusing on the type structure of the data being reconciled. Thislinguistic perspective may offer new insights into classical problems inthese areas, such as the well known "view update problem" in databases.At the same time, reconciling complex abstract formats, such as orderedlists and trees, brings to fore a number of algorithmic issuesconcerning how to meaningfully weave together disconnected changes inreplicas.