12. Merging

Video created from my 790-063 (http://www.cs.unc.edu/~dewan/790-063/current/) Fall 14 lectures. See https://mix.office.com/watch/15c84c46xrnea for a slide-based structured "video", http://www.cs.unc.edu/~dewan/790-063/current/Slides/12_Merging.pptx for the original PPTX and http://www.cs.unc.edu/~dewan/790-063/current/Slides/12_Merging.pdf for the pdf

1.0x

12. Merging

Created 3 years ago

Duration 0:40:31
lesson view count 14
Video created from my 790-063 (http://www.cs.unc.edu/~dewan/790-063/current/) Fall 14 lectures. See https://mix.office.com/watch/15c84c46xrnea for a slide-based structured "video", http://www.cs.unc.edu/~dewan/790-063/current/Slides/12_Merging.pptx for the original PPTX and http://www.cs.unc.edu/~dewan/790-063/current/Slides/12_Merging.pdf for the pdf
Select the file type you wish to download
Slide Content
  1. Merge Policies

    Slide 1 - Merge Policies

    • Prasun Dewan
    • Department of Computer Science
    • University of North Carolina at Chapel Hill
    • dewan@cs.unc.edu
  2. 5

    Slide 2 - 5

    • 0
    • I,6, ?
    • Concurrent Interaction
    • PC
    • 1
    • PC
    • 2
    • 0
    • 0
    • 4
    • 0
    • 5
    • 0
    • 5
    • 0
    • I,6, ?
    • I,6, ?
    • 5
    • 0
    • I,6, ?
    • l
    • u
    • n
    • c
    • 1
    • 2
    • 3
    • 4
    • 5
    • h
    • ?
    • 6
    • l
    • u
    • n
    • c
    • 1
    • 2
    • 3
    • 4
    • 5
    • h
    • 6
    • ?
    • Insert same character at same position?
  3. 5

    Slide 3 - 5

    • 0
    • I,6, ?
    • Concurrent Interaction
    • PC
    • 1
    • PC
    • 2
    • 0
    • 0
    • 4
    • 0
    • 5
    • 0
    • 5
    • 0
    • I,6, ?
    • I,6, ?
    • 5
    • 0
    • I,6, ?
    • l
    • u
    • n
    • c
    • 1
    • 2
    • 3
    • 4
    • 5
    • h
    • ?
    • 6
    • l
    • u
    • n
    • c
    • 1
    • 2
    • 3
    • 4
    • 5
    • h
    • 6
    • ?
    • ?
    • 7
    • 7
    • ?
    • Insert same character at same position?
    • Duplicate character!
    • I,6, ?
    • I,7, ?
    • Work preserving
    • Does not meet “user intention”
  4. 5

    Slide 4 - 5

    • 0
    • I,6, ?
    • Concurrent Interaction
    • PC
    • 1
    • PC
    • 2
    • 0
    • 0
    • 4
    • 0
    • 5
    • 0
    • 5
    • 0
    • I,6, ?
    • I,6, ?
    • 5
    • 0
    • I,6, ?
    • l
    • u
    • n
    • c
    • 1
    • 2
    • 3
    • 4
    • 5
    • h
    • ?
    • 6
    • l
    • u
    • n
    • c
    • 1
    • 2
    • 3
    • 4
    • 5
    • h
    • 6
    • ?
    • InsertOperation TransformInsertInsert (InsertOperation Remote, InsertOperation L ocal) {
    • Operation RemoteT = Remote.clone();
    • if (Remote.index == Local.index && Remote.element.equal(Local.element))
    • return NullOperation
    • if (Remote.index > Local.index ||
    • (Remote.index === Local.index && Remote.id < Local.id))
    • RemoteT.index = Remote.index + 1;
    • return RemoteT ;
    • }
    • Meets “user intention”
  5. Goal of Consistency

    Slide 5 - Goal of Consistency

    • At quiescence (no user interacting) all displays are the same
    • When concurrent command is executed, could ignore it and clear object
    • Meets TP1 (and TP2!)
    • Meets user intention
    • How to describe what it is?
    • Even if we cannot describe it, how to describe what algorithm does
    • More than one “reasonable” merge acceptable
    • Application-specific merger
    • Application-specific merge procedure
    • Declarative scheme?
  6. Assumptions and Intention Issue

    Slide 6 - Assumptions and Intention Issue

    • One-level sequence with inserts only.
    • Inserts at different positions are both accepted (as define by initial transformation functions).
    • If both users insert the same element at the same position, only one is executed.
    • What happens when both users insert different elements at the same position?
  7. Merge Matrix For Insertable Sequences

    Slide 7 - Merge Matrix For Insertable Sequences

    • Sequence
    • Insert(#)
    • Insert(#)
    • Server Operation at Same index
    • Client operation at same index
    • Cell Choices?
    • A particular algorithm can give the application and/or user a subset of choices in the merge matrix
    • Describes merge semantics of different insert operations at same index
    • Default value for flexible algorithm?
    • Merge matrix not relevant when indices are different or insertions are the same
  8. Concurrent Operation

    Slide 8 - Concurrent Operation

    • h
    • hi
    • h1
    • ???
    • User intention?
    • Conflict!
  9. Accept Both

    Slide 9 - Accept Both

    • Accept both as they can resolve the conflict
    • h
    • hi
    • h1
    • h1i
  10. Accept None

    Slide 10 - Accept None

    • Accept none as there is a conflict and cannot afford a wrong merge
    • h
    • hi
    • h1
    • h
  11. Accept Server

    Slide 11 - Accept Server

    • Accept earlier (server) so later person can see it and correct it
    • h
    • hi
    • h1
    • hi
  12. Accept Client

    Slide 12 - Accept Client

    • Accept later (client) as more recent information available
    • h
    • hi
    • h1
    • h1
  13. Merge Matrix For Insertable Sequences

    Slide 13 - Merge Matrix For Insertable Sequences

    • Sequence
    • Insert(#)
    • Insert(#)
    • Server Operation at Same index
    • Client operation at same index
    • Server
    • Client
    • None
    • Both
    • Cell Choices
    • A particular algorithm can give the application and/or user a subset of choices in the merge matrix
    • Describes merge semantics of different insert operations at same index
    • Default value for flexible algorithm?
    • Merge matrix not relevant when indices are different or insertions are the same
  14. Default for Insertable Sequences

    Slide 14 - Default for Insertable Sequences

    • Sequence
    • Insert(#)
    • Insert(#)
    • Both
    • Default value for flexible algorithm
    • Delete and Modify Operations?
    • Server
    • Client
    • None
    • Both
  15. Merge Matrix for Insertable Sequences

    Slide 15 - Merge Matrix for Insertable Sequences

    • Sequence
    • Insert(#)
    • Delete(#)
    • Replace(#)
    • Insert(#)
    • Delete(#)
    • Replace(#)
    • Server
    • Client
    • None
    • Both
    • Describes merge semantics of different sequence operations at same index
    • Default values for flexible algorithm?
  16. Defaults for General Sequences

    Slide 16 - Defaults for General Sequences

    • Deletes at the same index always the same operation and hence NoOp
    • Sequence
    • Insert(#, a)
    • Delete(#)
    • Replace(#)
    • Insert(#, b)
    • Both
    • Both
    • Both
    • Delete(#)
    • Both
    • NoOp
    • Server
    • Replace(#)
    • Both
    • Client
    • Server
    • Server
    • Client
    • None
    • Both
    • Replacement means it is relevant and perhaps should not be deleted
    • Tables?
  17. General Sequences and Replace/Delete

    Slide 17 - General Sequences and Replace/Delete

    • bat
    • cat
    • at
    • Replace(1, “c’)
    • Delete(1, “c’)
    • cat
  18. Table Matrix

    Slide 18 - Table Matrix

    • Table
    • Put (key)
    • Delete(key)
    • Put (key)
    • Delete(key)
    • Server
    • Client
    • None
    • Both
    • Describes merge semantics of different table operations at key
    • Default values?
    • Assume operations at different keys are non conflicting
  19. Defaults for General Tables

    Slide 19 - Defaults for General Tables

    • Putting the same value at the same key is a NoOP
    • Table
    • Put (key)
    • Delete(key)
    • Put (key)
    • Server
    • Client
    • Delete(key)
    • Server
    • NoOp
    • Server
    • Client
    • None
    • Both
  20. Tables

    Slide 20 - Tables

    • put (“bob, false)
    • remove (“bob”)
  21. Record Matrix

    Slide 21 - Record Matrix

    • Putting the same value at the same property is a NoOP
    • Record
    • Set (Property)
    • Set (Property)
    • Server
    • Client
    • None
    • Both
    • Describes merge semantics of different record operations at same property
    • Default value?
  22. Defaults for Record

    Slide 22 - Defaults for Record

    • Record
    • Set (Property)
    • Set (Property)
    • Server
    • Server
    • Client
    • None
    • Both
    • Accept earlier (server) so later person can see it and correct it
  23. Beans/Records

    Slide 23 - Beans/Records

    • set (“ticketPrice”, 24.0)
    • set (“ticketPrice”, 24.1)
  24. Atomic Objects

    Slide 24 - Atomic Objects

    • Accept earlier (server) so later person can see it and correct it
    • 23.5
    • 24
    • 24.1
    • 24.1
    • set (24.0)
    • set (24.1)
  25. Atomic Matrix

    Slide 25 - Atomic Matrix

    • Atomic
    • Set ()
    • Set ()
    • Server
  26. General Merge Matrix

    Slide 26 - General Merge Matrix

    • Type
    • Operation1
    • OperationN
    • Operation1
    • Default11
    • ...
    • Default1N
    • OperationN
    • DefaultN1
    • DefaultNN
    • Some type-specific operand (index, key, value) whose value determines when two dissimilar operations are compared
    • Server
    • Client
    • None
    • Both
  27. Asynchronous Buffered Changes

    Slide 27 - Asynchronous Buffered Changes

    • Joe
    • UNC
    • Joe
    • UNC-
    • Joe
    • UNC-C
    • Joe
    • UNC-CH
    • Joe
    • UNCC
    • Joe
    • UNCC-CH
    • Can we extend model to add the option of accepting all of server or client changes to affiliation?
    • “Joe” and “UNC” are sequences in a record with name and affiliation properties
    • Need to capture multiple levels of changes
  28. Slide 28

    • Hierarchical Document
    • Record
    • J
    • o
    • e
    • U
    • N
    • C
    • Sequence
    • Set(Affiliation)
    • I(4, ‘-’)
    • Name
    • Affiliation
    • Sequence
    • Record
    • J
    • o
    • e
    • U
    • N
    • C
    • Sequence
    • Name
    • Affiliation
    • Sequence
    • Record
    • J
    • o
    • e
    • U
    • N
    • C
    • Sequence
    • Name
    • Affiliation
    • Sequence
    • -
    • C
    • H
    • C
    • I(5, ‘C’)
    • I(6, ‘H’)
    • Set(Affiliation)
    • I(4, ‘C’)
  29. Slide 29

    • Level 1 Step
    • Record
    • J
    • o
    • e
    • U
    • N
    • C
    • Sequence
    • Set(Affiliation)
    • I(4, ‘-’)
    • Name
    • Affiliation
    • Sequence
    • Record
    • J
    • o
    • e
    • U
    • N
    • C
    • Sequence
    • Name
    • Affiliation
    • Sequence
    • Record
    • J
    • o
    • e
    • U
    • N
    • C
    • Sequence
    • Name
    • Affiliation
    • Sequence
    • C
    • C
    • H
    • C
    • I(5, ‘C’)
    • I(6, ‘H’)
    • Set(Affiliation)
    • I(4, ‘C’)
    • U
    • N
    • C
    • C
    • Hot to go to next level?
    • Record
    • Set (Property)
    • Set (Property)
    • Server
  30. Merge Next Level Option

    Slide 30 - Merge Next Level Option

    • Type
    • Operation1
    • OperationN
    • Operation1
    • Default11
    • ...
    • Default1N
    • OperationN
    • DefaultN1
    • DefaultNN
    • Server
    • Client
    • None
    • Both
    • Merge
  31. Slide 31

    • Level 1 Step
    • Record
    • J
    • o
    • e
    • U
    • N
    • C
    • Sequence
    • Set(Affiliation)
    • I(4, ‘-’)
    • Name
    • Affiliation
    • Sequence
    • Record
    • J
    • o
    • e
    • U
    • N
    • C
    • Sequence
    • Name
    • Affiliation
    • Sequence
    • Record
    • J
    • o
    • e
    • U
    • N
    • C
    • Sequence
    • Name
    • Affiliation
    • Sequence
    • -
    • C
    • H
    • C
    • I(5, ‘C’)
    • I(6, ‘H’)
    • Set(Affiliation)
    • I(4, ‘C’)
    • Record
    • Set (Property)
    • Set (Property)
    • Merge
    • U
    • N
    • C
    • C
  32. Slide 32

    • Level 2 Step
    • Record
    • J
    • o
    • e
    • U
    • N
    • C
    • Sequence
    • Set(Affiliation)
    • I(4, ‘-’)
    • Name
    • Affiliation
    • Sequence
    • Record
    • J
    • o
    • e
    • U
    • N
    • C
    • Sequence
    • Name
    • Affiliation
    • Sequence
    • Record
    • J
    • o
    • e
    • U
    • N
    • C
    • Sequence
    • Name
    • Affiliation
    • Sequence
    • -
    • C
    • H
    • C
    • I(5, ‘C’)
    • I(6, ‘H’)
    • Set(Affiliation)
    • I(4, ‘C’)
    • U
    • N
    • C
    • C
    • Hot to go to next level?
    • Sequence
    • Insert(#)
    • Delete(#)
    • Replace(#)
    • Insert(#)
    • Both
    • Both
    • Both
    • Delete(#)
    • Both
    • NoOp
    • Server
    • Replace(#)
    • Both
    • Client
    • Server
    • -
    • C
    • H
  33. InsertOperation TransformInsertInsert (InsertOperation R, InsertOperation L)  {

    Slide 33 - InsertOperation TransformInsertInsert (InsertOperation R, InsertOperation L) {

    • Operation RT = deepClone();
    • if ((R.index > L.index) ||
    • (R.index === L.index && R.isServer()))
    • RT.index = R.index + 1;
    • return RT ;
    • }
    • Merge Matrix vs. Merge Procedures
    • InsertOperation TransformInsertInsert (InsertOperation R, InsertOperation L) {
    • Operation RT = deepClone();
    • if ((R.index > L.index) ||
    • (R.index === L.index && !R.isServer()))
    • RT.index = R.index + 1;
    • return RT ;
    • }
    • Sequence
    • Insert(#)
    • Delete(#)
    • Replace(#)
    • Insert(#)
    • Delete(#)
    • Replace(#)
    • Server
    • Client
    • None
    • Both
    • Procedural
    • Declarative
    • Declarative is higher level allows easy customization
    • But it is less expressive
  34. Merge Matrix

    Slide 34 - Merge Matrix

    • Covered all asynchronous merge policies known in 94-97
    • Had mechanisms to extend the default matrix
  35. Reference for Merge Matrix

    Slide 35 - Reference for Merge Matrix

    • Munson and Dewan ‘94, ’97
    • Showed that all merge procedures at that time for spreadsheets, file systems, databases, .. could be supported using the merge matrix
    • Merge matrix entry could itself have merge procedures in it for a specific combination of operations or level