$30 off During Our Annual Pro Sale. View Details »

Papers we Love PDX

Papers we Love PDX

Detection of Mutual Inconsistency in Distributed Systems

Caitie McCaffrey

June 28, 2016
Tweet

More Decks by Caitie McCaffrey

Other Decks in Technology

Transcript

  1. Detection of Mutual Inconsistency in
    Distributed Systems
    Papers We Love PDX - June 2016

    View Slide

  2. Caitie McCaffrey
    @caitie
    Distributed Systems Engineer
    caitiem.com

    View Slide

  3. 1983

    View Slide

  4. View Slide

  5. View Slide

  6. View Slide

  7. View Slide

  8. Replication for Availability

    View Slide

  9. “In some environments it is
    desirable or necessary to permit
    users to continue modifying
    resources such as files when the
    network is partitioned”

    View Slide

  10. “Files are not stored redundantly
    but are kept on removable storage
    media which can be carried around
    during prolonged partitions. Thus
    availability & consistency are
    simultaneously achieved”
    Disk Toting

    View Slide

  11. The Partitioning Problem

    View Slide

  12. The Partitioning Problem

    View Slide

  13. The Partitioning Problem

    View Slide

  14. The Partitioning Problem

    View Slide

  15. How Do We Detect Inconsistencies?
    The Partitioning Problem

    View Slide

  16. Paper Goals
    Do Not Restrict Availability of
    Systems during Partition
    Effectively Detect Mutual
    Inconsistencies

    View Slide

  17. Origin
    Points
    Version
    Vectors
    &

    View Slide

  18. Origin Points
    • System wide unique identifier generated when
    the file is created
    • Immutable attribute of the file
    • Suggested: Creation Time & Creation Site Pair
    • Detect Name Conflicts

    View Slide

  19. Name Conflicts
    B
    A

    View Slide

  20. Name Conflicts
    B
    A

    View Slide

  21. Name Conflicts
    B
    A
    Conflict!

    View Slide

  22. Version Conflicts
    C
    C

    View Slide

  23. Version Conflicts
    C
    C

    View Slide

  24. Version Conflicts
    C
    C

    View Slide

  25. Version Conflicts
    C
    C
    Origin Points are
    Not Enough

    View Slide

  26. What about TimeStamps?

    View Slide

  27. Version Conflicts
    T0
    T0

    View Slide

  28. Version Conflicts
    T0
    T0

    View Slide

  29. Version Conflicts
    T0
    T0
    No Conflict!

    View Slide

  30. Version Conflicts
    T0
    T0

    View Slide

  31. Version Conflicts
    T0
    T1

    View Slide

  32. Version Conflicts
    T0
    T1

    View Slide

  33. Version Conflicts
    T1
    T1
    No Conflict!

    View Slide

  34. “Each partition can break into sub
    partitions and/or merge with other
    partitions many times before the
    entire network finally becomes
    connected”
    The Partition Problem

    View Slide

  35. ABCD
    Partition Graph
    T0

    View Slide

  36. ABCD
    AB CD
    Partition Graph
    T0
    T0
    T0

    View Slide

  37. ABCD
    AB CD
    Partition Graph
    T0
    T0
    T1
    T2

    View Slide

  38. ABCD
    AB CD
    D
    BC
    A
    Partition Graph
    T0
    T0
    T0
    T1
    T1

    View Slide

  39. ABCD
    AB CD
    D
    BC
    A
    Partition Graph
    T0
    T0
    T0
    T1
    T1
    No Conflict!
    T1

    View Slide

  40. ABCD
    AB CD
    D
    BC
    A
    Partition Graph
    T0
    T0
    T0
    T1
    T1
    T2

    View Slide

  41. ABCD
    AB CD
    D
    BC
    A
    BCD
    Partition Graph
    T0
    T0
    T0
    T1
    T1
    T2

    View Slide

  42. ABCD
    AB CD
    D
    BC
    A
    BCD
    Partition Graph
    T0
    T0
    T0
    T1
    T1
    T2
    Conflict!

    View Slide

  43. ABCD
    AB CD
    D
    BC
    A
    BCD
    Partition Graph
    T0
    T0
    T0
    T2
    T1
    T3
    T2

    View Slide

  44. ABCD
    AB CD
    D
    BC
    A
    BCD
    ABCD
    Partition Graph
    T0
    T0
    T0
    T2
    T1
    T3
    T2
    T2

    View Slide

  45. ABCD
    AB CD
    D
    BC
    A
    BCD
    ABCD
    Partition Graph
    T0
    T0
    T0
    T2
    T1
    T3
    T2
    T2
    Conflict!

    View Slide

  46. “What is more difficult is
    to find a mechanism which
    detects version conflicts
    only when they are real”

    View Slide

  47. Version Vectors
    “A Version Vector for a file f is a sequence of n
    pairs, where n is the number of sites at which f
    is stored … the ith vector entry counts the
    number Vi of updates to f made at site Si”

    View Slide

  48. Compatible Version Vectors


    View Slide

  49. Incompatible Version Vectors


    View Slide

  50. Version Vectors
    • For each update of f on site Si we increment
    the Sith component of the version vector
    • When conflicts are reconciled the Max Sith
    entry is set in the version vector
    • Version vectors encode the partial order
    defined by the partition graph

    View Slide

  51. ABCD
    Partition Graph
    C:0, D:0>

    View Slide

  52. ABCD
    AB CD
    Partition Graph
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>

    View Slide

  53. ABCD
    AB CD
    Partition Graph
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>

    View Slide

  54. ABCD
    AB CD
    D
    BC
    A
    Partition Graph
    T2
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>

    View Slide

  55. ABCD
    AB CD
    D
    BC
    A
    Partition Graph
    T2
    C:0, D:0>

    C:0, D:0>

    C:0, D:0>
    No Conflict!

    View Slide

  56. ABCD
    AB CD
    D
    BC
    A
    Partition Graph
    T2
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>

    View Slide

  57. ABCD
    AB CD
    D
    BC
    A
    Partition Graph
    T2
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:1, D:0>

    View Slide

  58. ABCD
    AB CD
    D
    BC
    A
    BCD
    Partition Graph
    T2
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:1, D:0>

    View Slide

  59. ABCD
    AB CD
    D
    BC
    A
    BCD
    Partition Graph
    T2
    C:0, D:0>
    C:0, D:0>

    C:0, D:0>
    C:0, D:0>

    No Conflict!

    View Slide

  60. ABCD
    AB CD
    D
    BC
    A
    BCD
    Partition Graph
    T2
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:1, D:0>
    C:1, D:0>

    View Slide

  61. ABCD
    AB CD
    D
    BC
    A
    BCD
    Partition Graph
    T2
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:1, D:0>
    C:1, D:0>
    ABCD

    View Slide

  62. ABCD
    AB CD
    D
    BC
    A
    BCD
    ABCD
    Partition Graph
    T2
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>
    C:0, D:0>

    C:1, D:0>

    Conflict!

    View Slide

  63. Conflict Resolution
    “A conflict detection mechanism, while valuable,
    has increased effect if there is also a method for
    reconciling conflicts automatically”

    View Slide

  64. Conflict Resolution
    “Clearly, conflict reconciliation must take into
    account the semantics of the operations which
    were done to the data object in conflict”

    View Slide

  65. 1995

    View Slide

  66. 2011

    View Slide

  67. Thank You!
    @caitie

    View Slide

  68. Image Credits
    • https://thenounproject.com/search/?q=laptop
    +user&i=512528
    • https://thenounproject.com/term/user/512525/
    • https://thenounproject.com/search/?
    q=database&i=9658

    View Slide