Information Technology Reference
In-Depth Information
BasicSyncJoin
(
nw, m
1
,m
2
)
let
(
vv
1
,rs
1
,in
1
)=
nw
[
m
1
]
let
(
vv
2
,rs
2
,in
2
)=
nw
[
m
2
]
assume
m
2
∈ in
1
for each
[
uid → r
]
∈ rs
2
:
let
(
m, v
)=
r.gvsn
if
v ∈ vv
1
[
m
]
∧
(
uid ∈ rs
1
∨
rs
1
[
uid
]
<r
)
then
rs
1
[
uid
]:=
r
vv
1
:=
vv
1
∪ vv
2
Fig. 3.
Simplified synchronization
So far our transitions ensure that all versions in the version vectors are con-
secutive,
∀
[
m
→
vs
]
∈
vv .vs
=
{
1
,...,
max(
vs
)
}
.
(4)
The second observation is a basic property of the system: concurrent updates
to the same resource may be detected by at least one machine during
Basic-
SyncJoin
. Suppose that
m
1
and
m
2
,and
uid
are such that (
vv
1
,rs
1
,
)=
nw
[
m
1
],
(
vv
2
,rs
2
,
)=
nw
[
m
2
], and [
uid
rs
2
.When
m
1
installs
r
2
we would like to know whether
r
2
was derived from
r
1
,orif
r
2
was obtained
concurrently with
r
1
. The answer to whether
r
2
is concurrent with
r
1
turns out
to be simple;
r
2
is concurrent with
r
1
iff the version of
r
1
is not known to
m
2
:
→
r
1
]
∈
rs
1
,
[
uid
→
r
2
]
∈
r
1
.gvsn
∈
vv
2
(5)
To prove this property, we can add a history variable
rs
all
to each machine.
The history variable
rs
all
is a set of all records ever maintained by the machine.
If one prefers, one may view this as specifying the cone of causality. Every update
to the main set of records
rs
gets reflected by adding the updated record to
rs
all
.
In the operation
BasicSyncJoin
, take the union of
rs
all
and
rs
all
.Nowobserve
that invariant (2) also holds for
rs
all
.
Detection of concurrent update conflicts is useful when one wants to perform
conflict detection and resolution, either manually or automatically. DFS-R per-
forms the conflict resolution automatically, as replication is a continuous service,
but stores conflicting files in a designated folder. Conflict resolution is performed
on version vectors, so once a machine has performed conflict resolution and
merged version vectors, the conflict is no longer visible to other machines. A dif-
ferent scheme that works for detecting conflicts is by associating a hash-tree [7,8]
comprising of hashes of all the previous versions of a file. The size of the un-
rolled hash-tree is then proportional to the number of changes to the file, while
version vectors grow proportionally to the number of machines. If machines are
reasonably well synchronized, they do not need to unroll large hash trees from
remote peers.
Search WWH ::
Custom Search