12
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Directory Reconciliation

      Preprint
      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We initiate the theoretical study of directory reconciliation, a generalization of document exchange, in which Alice and Bob each have different versions of a set of documents that they wish to synchronize. This problem is designed to capture the setting of synchronizing different versions of file directories, while allowing for changes of file names and locations without significant expense. We present protocols for efficiently solving directory reconciliation based on a reduction to document exchange under edit distance with block moves, as well as protocols combining techniques for reconciling sets of sets with document exchange protocols. Along the way, we develop a new protocol for document exchange under edit distance with block moves inspired by noisy binary search in graphs, which uses only \(O(k \log n)\) bits of communication at the expense of \(O(k \log n)\) rounds of communication.

          Related collections

          Most cited references11

          • Record: found
          • Abstract: not found
          • Article: not found

          Private vs. common random bits in communication complexity

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Set reconciliation with nearly optimal communication complexity

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Interactive Communication of Balanced Distributions and of Correlated Files

                Bookmark

                Author and article information

                Journal
                25 July 2018
                Article
                1807.09686
                b629a8e0-7578-4d66-8c2e-e614eb7742c9

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                cs.DS cs.DC

                Data structures & Algorithms,Networking & Internet architecture
                Data structures & Algorithms, Networking & Internet architecture

                Comments

                Comment on this article