Information Technology Reference
In-Depth Information
After a new node is added, the system will be reorganized to that in Figure 15.12. Now the
two new redundant data block, denoted by
c
0
,
1
and
c
1
,
1
, are computed from
4
c
0
,
1
=
f
2
,
j
+
1
v
j
(15.5)
j
=
0
and
9
c
1
,
1
=
f
2
,
j
−
5
+
1
v
j
(15.6)
j
=
5
Comparing equation (15.5) with equation (15.3) we can observe that they share four common
terms in
v
j
−
v
0
,v
1
,v
2
,v
3
. Hence we can rewrite equation (15.5) as follows:
3
c
0
,
1
=
f
2
,
j
+
1
v
j
+
f
2
,
5
v
4
j
=
0
=
c
0
,
1
+
f
2
,
5
v
4
(15.7)
In other words, we can compute
c
0
,
1
using the original redundant data
c
0
,
1
plus data block
v
4
.
Thus, instead of sending all five data blocks to redundant node
r
1
to perform redundant data
update, we now only need to send one data block, i.e.,
v
4
, thereby dramatically reducing the
overheads in updating the redundant data
c
0
,
1
.
15.4.3 Parity Group Reshuffling
In some cases, the previous straightforward reuse technique may not be applicable due to
differences in the coefficients
f
i
,
j
. For example,
c
1
,
1
is computed from
v
5
to
v
9
and share
common terms in
v
5
,v
6
, and
v
7
with
c
1
,
1
. Thus, it appears that we can reuse the common terms
v
9
to
r
1
to compute
c
1
,
1
. However, comparing the equations for
c
1
,
1
:
and send only
v
8
and
9
c
1
,
1
=
f
2
,
j
−
5
+
1
v
j
j
=
5
=
(
f
2
,
1
v
5
+
f
2
,
2
v
6
+
f
2
,
3
v
7
)
+
f
2
,
4
v
8
+
f
2
,
5
v
9
(15.8)
and for
c
1
,
1
:
7
c
1
,
1
=
f
2
,
j
−
4
+
1
v
j
j
=
4
=
f
2
,
1
v
4
+
(
f
2
,
2
v
5
+
f
2
,
3
v
6
+
f
2
,
4
v
7
)
(15.9)
we found that the common terms
v
7
now have different coefficients
f
i
,
j
(e.g.,
f
2
,
1
v
5
versus
f
2
,
2
v
5
). As a result, we cannot reuse
c
1
,
1
in computing
c
1
,
1
.
v
5
,
v
6
, and
Search WWH ::
Custom Search