Merge Types
draft-toomim-httpbis-merge-types-00

Document Type Active Internet-Draft (individual)
Last updated 2019-11-18
Stream (None)
Intended RFC status (None)
Formats plain text pdf htmlized bibtex
Stream Stream state (No stream defined)
Consensus Boilerplate Unknown
RFC Editor Note (None)
IESG IESG state I-D Exists
Telechat date
Responsible AD (None)
Send notices to (None)
Internet-Draft                                                 M. Toomim
Expires: Mar 8, 2020                                   Invisible College
Intended status: Proposed Standard                        M. Milutinovic
                                                             UC Berkeley
                                                              B. Bellomy
                                                       Invisible College
                                                            Nov 18, 2019

                              Merge Types
                  draft-toomim-httpbis-merge-types-00

Abstract

   Merge Types specify how to merge multiple simultaneous edits to a
   resource.  This happens when two computers edit the same state over a
   network with latency.  A Merge Type specifies how to merge
   conflicting changes.  If the computers implement and agree upon the
   same Merge Type, then they can guarantee to reach a consistent state,
   after arbitrary edits, eventually.

   You can define new Merge Types.  This document defines Merge Types,
   the structure of the Merge Type system, and IANA registration
   procedures for Merge Types.




Status of this Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as
   Internet-Drafts.  The list of current Internet-Drafts is at
   http://datatracker.ietf.org/drafts/current/.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   https://www.ietf.org/1id-abstracts.html

   The list of Internet-Draft Shadow Directories can be accessed at
   https://www.ietf.org/shadow.html




Table of Contents

   1.  Introduction ...................................................4
      1.1. Merge Types vary across applications .......................4
      1.2. A Merge Type is specified as a function ....................5
   2. Definitions .....................................................5
   3. Merge Type Naming ...............................................5
   4. IANA Considerations .............................................6
      4.1. Merge Type Registry ........................................6
           4.1.1. Procedure ...........................................6
           4.1.2. Registrations .......................................6
           4.1.3. Comments on Merge Type Registrations ................6
           4.1.4. Change Procedures ...................................6
   5. Security Considerations .........................................7
   6. Conventions .....................................................8
   7. Copyright Notice ................................................8
   8. References ......................................................8
      8.1. Normative References .......................................8
      8.2. Informative References .....................................8



1.  Introduction

   In a version history, a merge type defines the output of a version
   that is derived from two or more parent versions:

                   _
             Time: |        birds
                   |        /   \
                   |     dogs   cats
                   |        \   /
                   V       dogcats   <-- merged version

   This can be ambiguous if two or more edits overlap, and edit the same
   thing in different ways. It is desireable if all computers resolve
   ambiguities in the same way, because then they will achieve
   consistent results.  In the example above, one person replaced "bird"
   with "dog", while the other replaced it with "cat", creating an
   ambiguity, which the Merge Type resolved by merging these edits
   together into "dogcats".  Some other Merge Type might resolve this
   ambiguity differently.

   Currently popular approaches are using conflict-free replicated data
   types [CRDT] or operational transformation [OT].  Different
   algorithms that merge in different ways.  Different applications need
   different parts of their data to merge in different ways.  The Merge
   Type specifies the outcome of a merge.  Different algorithms can
   implement the same Merge Type to interoperate.

   If a Merge Type is specified for a region of data, and all computers
   implement that Merge Type, then they can guarantee to obtain the same
   resulting state, no matter the order that events arrive over the
   network, or the algorithms they use to implement the Merge Types.

   This document defines how to specify a Merge Type within a
   standardized naming scheme.

1.1.  Merge Types vary across applications
Show full document text