idnits 2.17.1 draft-toomim-httpbis-merge-types-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 73 has weird spacing: '... dogs cats...' -- The document date (Nov 18, 2019) is 1620 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) ** Obsolete normative reference: RFC 5226 (Obsoleted by RFC 8126) Summary: 1 error (**), 0 flaws (~~), 2 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 Internet-Draft M. Toomim 2 Expires: Mar 8, 2020 Invisible College 3 Intended status: Proposed Standard M. Milutinovic 4 UC Berkeley 5 B. Bellomy 6 Invisible College 7 Nov 18, 2019 9 Merge Types 10 draft-toomim-httpbis-merge-types-00 12 Abstract 14 Merge Types specify how to merge multiple simultaneous edits to a 15 resource. This happens when two computers edit the same state over a 16 network with latency. A Merge Type specifies how to merge 17 conflicting changes. If the computers implement and agree upon the 18 same Merge Type, then they can guarantee to reach a consistent state, 19 after arbitrary edits, eventually. 21 You can define new Merge Types. This document defines Merge Types, 22 the structure of the Merge Type system, and IANA registration 23 procedures for Merge Types. 25 Status of this Memo 27 This Internet-Draft is submitted in full conformance with the 28 provisions of BCP 78 and BCP 79. 30 Internet-Drafts are working documents of the Internet Engineering 31 Task Force (IETF), its areas, and its working groups. Note that 32 other groups may also distribute working documents as 33 Internet-Drafts. The list of current Internet-Drafts is at 34 http://datatracker.ietf.org/drafts/current/. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 The list of current Internet-Drafts can be accessed at 42 https://www.ietf.org/1id-abstracts.html 44 The list of Internet-Draft Shadow Directories can be accessed at 45 https://www.ietf.org/shadow.html 46 Table of Contents 48 1. Introduction ...................................................4 49 1.1. Merge Types vary across applications .......................4 50 1.2. A Merge Type is specified as a function ....................5 51 2. Definitions .....................................................5 52 3. Merge Type Naming ...............................................5 53 4. IANA Considerations .............................................6 54 4.1. Merge Type Registry ........................................6 55 4.1.1. Procedure ...........................................6 56 4.1.2. Registrations .......................................6 57 4.1.3. Comments on Merge Type Registrations ................6 58 4.1.4. Change Procedures ...................................6 59 5. Security Considerations .........................................7 60 6. Conventions .....................................................8 61 7. Copyright Notice ................................................8 62 8. References ......................................................8 63 8.1. Normative References .......................................8 64 8.2. Informative References .....................................8 65 1. Introduction 67 In a version history, a merge type defines the output of a version 68 that is derived from two or more parent versions: 70 _ 71 Time: | birds 72 | / \ 73 | dogs cats 74 | \ / 75 V dogcats <-- merged version 77 This can be ambiguous if two or more edits overlap, and edit the same 78 thing in different ways. It is desireable if all computers resolve 79 ambiguities in the same way, because then they will achieve 80 consistent results. In the example above, one person replaced "bird" 81 with "dog", while the other replaced it with "cat", creating an 82 ambiguity, which the Merge Type resolved by merging these edits 83 together into "dogcats". Some other Merge Type might resolve this 84 ambiguity differently. 86 Currently popular approaches are using conflict-free replicated data 87 types [CRDT] or operational transformation [OT]. Different 88 algorithms that merge in different ways. Different applications need 89 different parts of their data to merge in different ways. The Merge 90 Type specifies the outcome of a merge. Different algorithms can 91 implement the same Merge Type to interoperate. 93 If a Merge Type is specified for a region of data, and all computers 94 implement that Merge Type, then they can guarantee to obtain the same 95 resulting state, no matter the order that events arrive over the 96 network, or the algorithms they use to implement the Merge Types. 98 This document defines how to specify a Merge Type within a 99 standardized naming scheme. 101 1.1. Merge Types vary across applications 103 Different resources merge in different ways, and can use different 104 merge types. For example, if a string represents a collaborative 105 text document, then parallel edits should be merged together. But if 106 a string represents a database entry ID and it is modified by two 107 requests simultaneously, the appropriate behavior is to choose one or 108 the other. 110 Similarly, if the resource is a number that represents a bank account 111 balance, then it should merge multiple simultaneous debits by adding 112 the amounts of the debits together. 114 Thus, it is nice to re-use a Merge Type across multiple types of 115 data; and each application has different needs for how its data 116 should merge. 118 1.2. A Merge Type is specified as a function 120 A Merge Type is a function that produces a merged state when provided 121 with any set of parent versions: 123 Merge Type 125 (parent, parent, ..) -> merged state 127 A Merge Type must be a deterministic function. Given the same set of 128 parents that descend from the same version history, it should always 129 return the same resulting merged state. This guarantees eventual 130 consistency. 132 To compute the result, a Merge Type has access to the entire version 133 history that preceded each of the parents, but it cannot depend on 134 information outside of that version history. 136 A Merge Type might only work on a particular Content-Type. For 137 instance, a "counter" Merge Type only works on numbers. A Merge Type 138 SHOULD state any limitations in the set of states that it is capable 139 of operating upon, and any assumptions it makes about the data. 141 But given that it has data that meets those assumptions, a Merge Type 142 MUST return a result when merging any set of versions. A Merge Type 143 cannot perform any validation on new versions. 145 2. Definitions 147 For the purpose of this document we define "synchronization" as the 148 resolution of conflicts. There are multiple approaches to resolving 149 conflicts and we define "Merge Type" an identifier that corresponds 150 to an approach of resolving conflicts. 152 3. Merge Type Naming 154 Naming of Merge Type follows naming requirements of media types as 155 described in Section 4.2. of [RFC6838] with the following exception: 156 Merge Type names consist only of a type-name without a sub-type. 158 Similarly, Merge Type parameters follow Section 4.3. of [RFC6838]. 160 Example: 162 automerge-counter 163 sharedb-json; variant=1 164 biggest-wins; sortby=versionid 165 4. IANA Considerations 167 4.1. Merge Type Registry 169 The "Merge Type Registry" defines the namespace for the merge type 170 names and refers to their corresponding specifications. The registry 171 will be created and maintained at 172 . 174 4.1.1. Procedure 176 Registration of a Merge Type MUST include the following fields: 178 o Type name 180 o Required parameters 182 o Optional parameters 184 o Description 186 o Security considerations 188 o Interoperability considerations 190 o Published specification 192 o Person & email address to contact for further information 194 Values to be added to this namespace require IETF Review (see 195 [RFC5226], Section 4.1). 197 4.1.2. Registrations 199 4.1.3. Comments on Merge Type Registrations 201 Comments on registered Merge Types may be submitted by members of the 202 community to the IANA at iana@iana.org. These comments will be 203 reviewed by the Merge Types reviewer and then passed on to the 204 "owner" of the Merge Type if possible. Submitters of comments may 205 request that their comment be attached to the Merge Type registration 206 itself; if the IANA, in consultation with the Merge Types reviewer, 207 approves, the comment will be made accessible in conjunction with the 208 type registration. 210 4.1.4. Change Procedures 212 Once a Merge Type has been published by the IANA, the owner may 213 request a change to its definition. The same procedure that would be 214 appropriate for the original registration request is used to process 215 a change request. 217 Merge Type registrations may not be deleted; Merge Types that are no 218 longer believed appropriate for use can be declared OBSOLETE; such 219 Merge Types will be clearly marked in the list published by the IANA. 221 Significant changes to a Merge Type's definition should be requested 222 only when there are serious omissions or errors in the published 223 specification. When review is required, a change request may be 224 denied if it renders entities that were valid under the previous 225 definition invalid under the new definition. 227 The owner of a Merge Type may pass responsibility to another person 228 or agency by informing the IANA; this can be done without discussion 229 or review. 231 The IESG may reassign responsibility for a Merge Type. The most 232 common case of this will be to enable changes to be made to types 233 where the author of the registration has died, moved out of contact, 234 or is otherwise unable to make changes that are important to the 235 community. 237 5. Security Considerations 239 An analysis of security issues SHOULD be done for all registered 240 Merge Types. However, regardless of what security analysis has or 241 has not been done, all descriptions of security issues MUST be as 242 accurate as possible. In particular, the security considerations 243 MUST NOT state that there are "no security issues associated with 244 this Merge Type". Security considerations for Merge Types MAY state 245 that "the security issues associated with this Merge Type have not 246 been assessed". 248 There is absolutely no requirement that Merge Types registered be 249 secure or completely free from risks. Nevertheless, all known 250 security risks MUST be identified in the registration of a Merge 251 Type. 253 The security considerations section of all registrations is subject 254 to continuing evaluation and modification, and in particular MAY be 255 extended by use of the "comments on Merge Types" mechanism described 256 in Section 4.1.3 above. 258 Some of the issues that need to be examined and described in a 259 security analysis of a Merge Type are: 261 o Merge Types might operate in a way that, while not directly 262 harmful, may result in disclosure of information that either 263 facilitates a subsequent attack or else violates user's privacy 264 in some way. 266 o A Merge Type should be considered in concert with a Validator. 267 For instance, it is possible for two transactions A and B to both 268 be valid individually, but when merged, the result is not valid. 269 For instance, if a bank account has $1, then two simultaneous 270 debits of $1 are both valid individually, but the resulting 271 merger, yielding -$2, drains the bank account balance below $0. 272 This is the double-spend problem. A system using Merge Types 273 SHOULD be aware of how its Merge Types interact with its 274 Validators. 276 6. Conventions 278 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 279 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 280 document are to be interpreted as described in [RFC2119]. 282 7. Copyright Notice 284 Copyright (c) 2019 IETF Trust and the persons identified as the 285 document authors. All rights reserved. 287 This document is subject to BCP 78 and the IETF Trust's Legal 288 Provisions Relating to IETF Documents 289 (http://trustee.ietf.org/license-info) in effect on the date of 290 publication of this document. Please review these documents 291 carefully, as they describe your rights and restrictions with respect 292 to this document. Code Components extracted from this document must 293 include Simplified BSD License text as described in Section 4.e of 294 the Trust Legal Provisions and are provided without warranty as 295 described in the Simplified BSD License. 297 8. References 299 8.1. Normative References 301 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 302 Requirement Levels", BCP 14, RFC 2119, March 1997. 304 [RFC6838] Freed, N., Klensin, J., and T. Hansen, "Media Type 305 Specifications and Registration Procedures", BCP 13, RFC 306 6838, January 2013. 308 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 309 IANA Considerations Section in RFCs", BCP 26, RFC 5226, 310 May 2008. 312 8.2. Informative References 314 [CRDT] Shapiro, M., Preguica, N., Baquero, C., and M. Zawirski, 315 "Conflict-free replicated data types", in SSS'11 316 Proceedings of the 13th international conference on 317 Stabilization, safety, and security of distributed 318 systems, October 2011. 320 [OT] Ellis, C. A., and S. J. Gibbs, "Concurrency control in 321 groupware systems", in SIGMOD '89 Proceedings of the 1989 322 ACM SIGMOD international conference on Management of data, 323 June 1989. 325 Authors' Addresses 327 For more information, the authors of this document are best contacted 328 via Internet mail: 330 Michael Toomim 331 Invisible College, Berkeley 332 2053 Berkeley Way 333 Berkeley, CA 94704 335 EMail: toomim@gmail.com 336 Web: https://invisible.college/@toomim 338 Mitar Milutinovic 339 UC Berkeley, EECS Department 340 775 Soda Hall #1776 341 Berkeley, CA 94720-1776 343 EMail: mitar.ietf@tnode.com 344 Web: https://mitar.tnode.com/ 346 Bryn Bellomy 347 Invisible College, Berkeley 348 2053 Berkeley Way 349 Berkeley, CA 94704 351 EMail: bryn@signals.io 352 Web: https://invisible.college/@bryn