Conflict resolution

Commit ordering rules

Building a logical view is equivalent to merging several chains of commits into one unified log. The ordering of commits obeys these rules.

• Commits with larger timestamps goes after those with smaller timestamps.
• If one commit goes before another commit in one peer, their order cannot be revered.
• If timestamps are indistinguishable, merge these commits into one using commit merging rules.

Commit merging rules

• Apply operations in this order: copy, creation, modification, and then deletion.
• If duplicated creations occur, the one from smallest md5 hash (in dictionary order) takes effect. This rule applies to modification and copy.

Suppose Resol and Reep have commits with identical timestamps.

• Resol’s log

  # commit X
  [new_file]
  both_create.txt
  create_and_delete.txt
  [modified]
  both_modify.txt
  [copied]
  [deleted]
  (MD5)
  both_create.txt 81dfcbafb6beab0729f6a6a504cc429b
  both_modify.txt 60b725f10c9c85c70d97880dfe8191b3
  create_and_delete.txt 3b5d5c3712955042212316173ccf37be
  (timestamp)
  1541611000000
  

• Reep’s log

  # commit Y
  [new_file]
  both_create.txt
  [modified]
  both_modify.txt
  [copied]
  from.txt => to.txt
  [deleted]
  create_and_delete.txt
  (MD5)
  both_create.txt b924cc405aca6f9270baeb6beabcfd15
  both_modify.txt 2cd6ee2c70b0bde53fbe6cac3c8b8bb1
  (timestamp)
  1541611000000
  

By merging these commits during replay, it results to the commit:

• Merged commit

  # commit Z
  [new_file]
  both_create.txt
  create_and_delete.txt
  [modified]
  both_modify.txt
  [copied]
  from.txt => to.txt
  [deleted]
  create_and_delete.txt
  (MD5)
  both_create.txt 81dfcbafb6beab0729f6a6a504cc429b
  both_modify.txt 2cd6ee2c70b0bde53fbe6cac3c8b8bb1
  create_and_delete.txt 3b5d5c3712955042212316173ccf37be
  (timestamp)
  1541611000000
  

  (Update 4) In the logical view, we have both_create.txt from Resol, both_modify.txt from Reep, copied file to.txt, and original from.txt. The create_and_delete.txt file never appears in the filesystem.

Conflict resolution

Operations in any of these cases don’t take effect.

• Creation on an existing file
• Deletion or modification on a non-existing file
• Copying from a non-existing file

Note that copying to a existing file can replace that file.

For example, Resol creates openme.txt and then modifies it, and Reep deletes it before Resol’s modification. According to our rule, Resol’s modification has no effect.

• Resol’s log

  # commit 1
  [new_file]
  openme.txt
  [modified]
  [copied]
  [deleted]
  (MD5)
  openme.txt 5c5602054a9f08648bc18189b2310f93
  (timestamp)
  1541611000000
    
  # commit 2
  [new_file]
  [modified]
  openme.txt
  [copied]
  [deleted]
  (MD5)
  openme.txt 39f0132b98181cb84680f9a4502065c5
  (timestamp)
  1541611050000
  

• Reep’s log

  # commit 1
  [new_file]
  [modified]
  [copied]
  [deleted]
  openme.txt
  (MD5)
  (timestamp)
  1541611030000