Locating Corruptions in a Replicated File in a Distributed Environment.
When a data file is replicated at more than one site, it is of interest to detect corruption by comparing the multiple copies. In order to reduce the amount of messaging for large files, techniques based on page signatures and combined signatures have been explored. However, for 3 or more sites, the known methods assume that the number of corrupted page copies is at most M/2  1, where M is the number of sites. This is a pessimistic assumption which is unrealistic. In this paper, this assumption is replaced by another assumption which is shown to be reasonable. Based on this assumption, and based on a finer model of the system, three distributed algorithms are derived, which can either improve the performance or provide more tolerance to corruptions compared to previous methods. As in some previous work, the amount of signature transmission in the algorithms varies according to the number and patterns of page copy corruptions that actually occur, and two of the algorithms achieve the optimal amount of signature transmission when no failure occurs.
Introduction
When a data file is replicated at one or more sites in a distributed computer net-
work, it is of interest to discover corruptions in the file copies by making comparison
among the multiple physical copies of the file. Since a data file is typically large,
it is inefficient to transmit the entire file to a remote site for comparison. The
methods using combined signatures tackle this problem as follows. Since each page
in a file may be large, a more concise representation, called a page signature is computed
based on the information stored in each page. The size of a page signature is
typically much smaller than the size of the page, though some information may be
lost in the compression. From the page signatures, combined signatures are computed
and transmitted among sites. The corruptions are detected by performing
some computations on the set of combined signatures. Each combined signature is
derived from the entire set of page signatures, and typically the number of combined
signatures needed for corruption detection is smaller than the total number
of page signatures. Hence this method uses less signature transmission compared
to methods using only page signatures.
Previous work caters for the worst case scenario in which the page signatures
for corrupted copies can be identical. Due to this consideration, the number of
corrupted page copies is assumed to be at most dM=2e\Gamma1, where M is the number of
sites. It is noted that when the number of pages is large, which is a basic assumption
motivating the method of combined signatures, this assumption is unrealistic. In
this paper, it is argued that the chance of 2 page copies being corrupted and having
identical page signatures is small and comparable to the tolerable probability of
two differing pages having the same page signature. Thus here it is assumed that 2
corrupted page copies do not have the same signature. With the new assumption,
and with a finer model of the system, 3 distributed algorithms are derived that
either need to transmit a smaller number of signatures or have greater tolerance
of corruption. Two of the algorithms are shown to achieve the minimal number of
signature transmission when no failure occurs. One of the algorithms (Algorithm
GF SIG A) has been presented in [6].
The paper is organized as follows: Section 2 describes the problem and previous
work. Section 3 is a description of some properties of the combined signatures
that will be useful for the algorithms that follow. Section 4 presents the distributed
algorithms. Section 5 is a performance analysis and comparison with previous work.
Section 6 gives a lower bound of the problem in non-faulty case and optimality of
the algorithms with respect to this. Section 7 relaxes some restrictions. Concluding
remarks are given in Section 8.
2. Problem Definition
Consider the case where a file is replicated among a set of M sites g.
Assume that the file contains N pages, fP 1 ; :::; PN g, and the copy of page P i at site
s j is P i;j . Some previous work has assumed centralized control so that communication
is always between a coordinator and the other sites. In this paper decentralized
control is assumed so that any site can communicate with any other site.
LOCATING CORRUPTIONS IN A REPLICATED FILE 3
When there is no failure, the copies of each page are identical. When there is one
or more site failures, some page copies may become corrupted. As in most previous
papers, it is assumed that the total number of corrupted page copies will not exceed
f . Furthermore, it is assumed that each site contains at most h corrupted page
copies, and at most g sites have corruption. If these values are not known, then h
is set to minfN; fg, and g is set to a greatest possible value.
The file size is assumed large, hence it is not cost-effective if the entire file copies
are transmitted among the sites. A known approach is to compute a page signature
for each page copy, and transmit and compare the signatures instead. The page
signature is typically much smaller than the page. For example [8] proposed to use a
parity structure for the page signatures. Two pages with different page signatures
are definitely not identical, but two pages that are different may happen to be
translated into the same page signature. However the chance of this happening
can be made small by making the signature size large. By exchanging the page
signatures among the sites, it is possible to discover corruption.
The number of page signatures may still be large. To further reduce the amount
of messages that need to be sent around, each site could compute a number of
combined signatures from the page signatures. For example, the combined signature
can be a bit-wise exclusive OR of a number of page signatures. Hence the
number of combined signatures will be smaller than the number of page signatures.
By exchanging the combined signatures the corrupted pages are determined. Another
way to compute the combined signatures is based on an error-correcting code
over some finite field and is introduced in [9, 11]. In particular, a method using
Reed-Solomon codes [5] has been suggested in [11] for problems with only 2 sites.
[1] extended the method of Reed-Solomon codes and solves the problem for M
replicated sites, where M - 3.

Table

1 summarizes the characteristics of a number of previous work for this
problem. In Table 1, N is the number of pages in the file, a1 is the assumption
that an uncorrupted copy resides in a known site, and a2 is the assumption that N
is a power of 2.
Algorithm # copies
failures
(centralized)

Table

1: results of previous work
The following are notations used in this paper
N number of pages in the file,
M number of sites, M - 3
b number of bits in each page signature
of the file
P i;j copy of page P i at site s j
page signature of page copy P i;j
sig j;m a combined signature for site s m where j is an integer
ff a primitive element in the finite field GF used to find a combined
signature
f maximum number of corrupted page copies in all sites at file
comparison
maximum number of sites that contain corrupted page copies at
file comparison
h maximum number of corrupted page copies at a site at file comparison

Table

Notations
Although [1] solves a more general problem for M copies of the file, it makes the
following assumption.
Assumption Z: M - 2f + 1.
LOCATING CORRUPTIONS IN A REPLICATED FILE 5
Assumption Z is made for the worst case consideration:
Consideration Z: the page signatures for corrupted copies of a page can be
identical.
The condition in consideration Z implies one of the following cases:
1. two or more copies of the same page happen to be corrupted with identical error
pattern, or
2. two or more copies of the same page are corrupted with different error patterns,
but their page signatures turn out to be the same.
Note that the use of the method of page signatures comes with the tolerance of a
problem related to the second case, in that a page copy may be corrupted so that
its content is different from a correct copy, but the page signature generated for it
happens to be identical to that of a correct copy, in which case, the method fails
to identify the corruption.
If corrupted copies of a page can be identical, then it must be the case that
in order to identify a correct version. This is because if M ! 2f
and a majority number of sites has failed at the same page, then a majority of the
page signatures (the corrupted ones) of this page can be identical and there is no
way to tell whether the corresponding copies are corrupted.
Consider some realistic figures for M and N . Suppose
f is at most 2, that is, Assumption Z says that at most 2 page copies
can be corrupted. As there are in total 10,000 page copies, and memory corruption
may occur in burst modes, one sees that this may not be a reasonable assumption.
It can be concluded that Assumption Z is unrealistic, and that an algorithm based
on this assumption and Consideration Z is probably a design with over-precaution.
One would then consider if Consideration Z can be ignored. For example, can one
instead assume that the page signatures for any 2 corrupted copies of the same
page will not be identical? Here it is shown that such an assumption is reasonable.
In particular, This assumption is supported with the following arguments.
1. The probability P rob A that given any 2 corrupted page copies of the same page,
their error patterns are identical is very small.
2. The probability P rob B that given any 2 corrupted page copies of the same page
with different error patterns, their page signatures are the same is very small.
3. The use of page signatures has an inherent probability of assigning a corrupted
page copy to the same page signature as a correct page copy, which has been
6 WAICHEE FU AND SIU-CHEUNG CHAU
claimed acceptable in previous work such as [3, 1, 11, 10]. Therefore, the probability
rob C that given a correct page copy and a corrupted page copy, they
are given the same page signatures is assumed negligible. P rob A and P rob B
will be shown to be no greater than P rob C , and hence P rob A and P rob B should
also be negligible.
The argument is based on the assumption that site failures are independent.
Suppose that each page of the file has b bits, then there are different possible
error patterns, it is assumed that the chance of occurrence of each pattern is the
same.
Probability of a given corrupted page copy having a given error pattern (say
Probability of 2 given corrupted page copies having the same given error pattern
Since there are choices of the error patterns X in the above, probability
of 2 given corrupted page copies having the same error
. For reasonable values of b, this probability is very
small.
Next consider the value of P rob B . Suppose that for an acceptable method, the
probability that 2 different page copies being given identical page signatures is x.
Therefore the probability P rob C that given a correct page copy and a corrupted
page copy, they are given the same page signatures is x. The probability P rob B that
given 2 corrupted page copies with different error patterns, their page signatures
are the same is also x. Since P rob C is negligible, P rob B is also negligible.
Finally note that P rob A is comparable to acceptable values of P rob C . For exam-
ple, for the algorithm given in [8], suppose each signature has c bits, if the parity
rules are chosen at random and the replicated file copies differ in a random fashion,
there would be a probability of 2 \Gammac that two page copies with different contents
have the same page signature, or P rob
for this page signature method. For a
40-bit parity parity sequence suggested in the paper, this probability will be about
. The value of b is typically large compared to c, for example, in [8], the
method is illustrated with
is typically much smaller than P rob C . Hence P rob A is negligible.
This paper thus put forward the proposal that the probability of 2 corrupted pages
having the same page signature is negligible. It will be seen that this relaxation
LOCATING CORRUPTIONS IN A REPLICATED FILE 7
leads to algorithms with better performance or fault-tolerance. The assumption in
this paper is the following:
Assumption A: The probability that any 2 corrupted copies of the same page
have identical page signatures is negligible.
Assumption A is based on a more basic assumption:
Assumption B: site failures are independent.
Assumption B may not hold if, for example, some copies are obtained from duplicating
another. However, in such cases, it is not obvious that a feasible corruption
detection method exists, since a majority of the copies may be corrupted.
3. Properties of Combined Signatures
We shall adopt the combined signature techniques as in [11, 3, 1]. In this method,
each site s A calculates a page signature S(P i;A ) for each of its page copies P i;A . For
this method to work, it must be the case that N ! 2 b , where b is the number of bits
of a page signature. Since there are 2 b possible values of page signatures, each page
signature can be considered as an element in a finite field (Galois field) GF (2 b ).
From these page signatures, s A can further compute combined signatures of b
bits.
Suppose a site s A with a file copy FA =! P 1;A ; :::; PN;A ? computes k combined
signatures. These combined signatures are given by
where ff is a primitive element in GF (2 b ) and the addition and multiplication
operations are those of GF (2 b ). Hence the elements are
distinct. Note that ff
ff. There are 2 b possible values for a
combined signature. We refer to the signatures sig j;A for
as the first k combined signatures.
To help explain the algorithm in the next section, a few properties of the combined
signatures are first described. In the algorithm two sets of combined signatures from
two different sites s A and s B are compared. In a special case, suppose the first N
combined signatures in each site are computed, and it is known that one of the
sites, say s A , is correct. The two sets of signatures are given by
If site s A sends its first N combined signatures to site s B , then s B can compute the
difference between sig j;A and sig j;B for 1. The difference between
the two sets is given by
Equation (1) can be written in a matrix
only if the signatures S(P i;A ) and
We see that E j is in GF (2 b ). ThenB
In the above, the left most matrix is a Vandermonde matrix. A Vandermonde
matrix is a matrix of the
LOCATING CORRUPTIONS IN A REPLICATED FILE 9
Theorem 7.2.1 of [5]: The above Vandermonde matrix has a nonzero determinant
if and only if all of the X i for are distinct. 2
Since the elements ff j are distinct, for 1 and it is assumed that
therefore the left most matrix in the above equation is nonsingular, and hence given
there is a unique solution for e i 's. If site s A contains no corruption, then the
non-zero e i 's identify the locations of page corruptions for site s B .
This property has been stated as follows:
Remark 1 [1]: For any given E the system of equations
has a unique solution for
Given the first N combined signatures sig i;C of a correct site
s C , for and the first N combined signatures sig i;A of a site s A , one
can solve the set of equations:
en ff
to identify the location of all corruptions in s A .
Observation 1 provides a way to detect errors at a corrupt site given a correct
site. However, in the beginning we do not know any correct site, a correct site
must first be discovered. Here a property of the combined signatures allows such
a discovery without the need of sending too many combined signatures. It will be
shown that if there are at most v errors located at a set of 2 sites, one needs only
compare the first v combined signatures of two sites to determine if they are both
correct or if at least one contains error. This property has been noted as follows:
has at most v non-zero entries.
If
The set of equations in Remark 2 can be written asB
ff
Remark 2 is based on the following argument. We note that the above equation
can be simplified if at most v of the e i 's are non-zero. We simplify by retaining only
the columns C i in the left most matrix for e i 6= 0. Suppose the columns indexed
remains. We form a square matrix by further extracting only
the rows with indices as in the following set of equations.B
We need only observe that e i j
trivial solution to the
above set of equations, which are also part of the solutions for the set of equation
in (3). The left-most matrix in (4) is a sub-matrix of the previous Vandermonde
matrix, one can show that this sub-matrix is non-singular by a similar proof as that
for Theorem 7.2.1 in [5]. Hence there is exactly one solution for the above matrix.
The set of equations in Remark 2 can be written asB
ff
Therefore, if the first v combined signatures for s A and s B are compared and
it is found that sig then the signatures S(P i;A ) and
are identical for all i's, and therefore the page copies P i;A and P i;B are also
identical. Since it is assumed (Assumption A) that two page copies of the same
page that are corrupted are not identical, it can only be the case that sites s A and
s B are both correct.
there can be at most v errors at 2 sites s A and s B , and the
first v combined signatures for s A and s B are identical, then sites s A and s B are
both correct.
Given that a correct site is found, from Remark 1, one can identify the corrupted
page copies if the first N combined signatures are computed. However, if it is known
LOCATING CORRUPTIONS IN A REPLICATED FILE 11
that the maximum number of corrupted page copies is not large, one can compute
and transmit fewer combined signatures. In order to do this, note the following
remark.
Remark 3 [1]: For any given E the
system of equations
1, has at most one solution
for than or equal to bJ=2c non-zero entries. This solution
can be obtained using a Reed-Solomon decoder [5].
In fact, only part of a Reed-Solomon decoder need to be utilized since it is of
interest to identify the location of errors rather than in correcting the combined
signatures for corrupted copies. Remark 3 is based on the following argument. First
assume on the contrary that there are 2 different solutions
N ), each having fewer than or equal to bJ=2c non-zero
e 0e 0:
Next subtract the second set of equations from the first set:B
entries, the vector entries. Hence
from Remark 2, we deduce that or the two sets of solutions
are in fact identical. Therefore the solution is unique.
If the first J combined signatures of a correct site s A and another
are given, and it is known that for s B there can be at most bJ=2c corrupted
page copies, then there is a unique solution for the system of J equations as described
in Remark 3, corresponding to the 2 set of combined signatures. The solution
identifies the locations of all the corruptions in s B .
4. Distributed Algorithms
The decentralized algorithm in [1] is considered since it achieves better performance.
Call this algorithm Algorithm GF SIG. Algorithm GF SIG works for M ? 2g,
since a majority number of sites will be correct and contain identical combined
signatures. However, since the algorithms are based on a very pessimistic consid-
eration, they may be using more message transmissions than necessary. In the first
proposed algorithm (Algorithm GF SIG A), the amount of messaging is reduced
mainly due to replacing Assumption Z and Consideration Z by Assumption A.
The second proposed algorithm (Algorithm GF SIG B) makes use of a more refined
model, which considers the parameter of h, the maximumnumber of corrupted
pages at a site. A further improvement on the number of message transmission is
achieved, given reasonable values of h.
Finally Algorithm GF SIG is modified to handle the case of M ?
Assumption A. The amount of message transmission is the same but the tolerance
of corruptions is greater than Algorithm GF SIG. Note that Algorithm GF SIG
cannot handle the case where M - 2g because in such cases there can be a majority
of sites that are corrupted, and Algorithm GF SIG will not be able to find a correct
site.
4.1. Algorithm GF SIG A
In this subsection, a distributed algorithm called Algorithm GF SIG A is pro-
posed. The parameter of h is not considered. Algorithm GF SIG A makes three
assumptions:
(1) Assumption A.
LOCATING CORRUPTIONS IN A REPLICATED FILE 13
2g.
(3) the number of sites is a multiple of 2.
The third assumption is made only for the sake of simplicity in presentation.
This can be readily relaxed : If the number of sites is odd, partition the set SS
into groups such that one and only one group has size 3, and the remaining groups
has size 2. The algorithm proceeds in much the same way and the performance
analysis is also similar.
Consider two different cases:
Case 1: N - f
The sites are first partitioned into groups of 2 sites, and the N page signatures
between the 2 sites in each group are compared. Any two page signatures that do
not agree indicates one or two corrupted copies. At the end of the comparison of
all groups, one must be able to locate at least one correct site since there must
be at least one group that contains two correct sites (see Lemma 2 at the end of
this subsection). The amount of signature transmission is given by dM=2eN . Let
FG be the set of groups that are found to contain some corruption. Suppose there
are F groups in FG. In the second phase, the correct site sends its page copies
to locate the corruptions in each of the groups in FG. The maximum number of
signatures sent for this purpose is bounded by FN . Hence the total number of
signature transmission is (dM=2e
Case 2: N ? f
For the procedure is shown in Figure 1. Most of the computations in

Figure

are based on the local view of a site s i1 . Lines (1)-(2), (19)-(21), and
(36)-(38) in

Figure

are where global computation or global consideration of some
kind is made.
For Case 2, Algorithm GF SIG A is made up of 2 phases. Phase 1 will either
discover that all sites are correct or locate at least one correct site. Phase 2 makes
use of the combined signatures of the correct site to detect corruptions.
A brief outline of the algorithm is first given:
1. Phase 1: partition the set of sites into groups of size 2 each, find a correct site
by comparison of some combined signatures between the 2 sites in each group.
14 WAICHEE FU AND SIU-CHEUNG CHAU
ALGORITHM GF SIG A:
Given: a set of sites SS.
Preprocessing Partition SS into groups of size 2.
Let the partitioning be
The followings are operations at site s i1 of G i .
Phase 1: Find a correct site
Else message
(5) SEND( message i ) to s j1 of all other groups G j .
j1 of all other groups G j .
Figure 1a: Phase 1 of distributed algorithm for detecting corruption
2. Phase 2: A set of groups FG will be found to contain corruptions. One site s i1
in each group G i in FG will be active, it receives the first f combined signatures
from a correct site found in Phase 1.
3. Phase 2 (cont.): s i1 solves a set of equation in order to detect corruptions if the
sites of this group has fewer than f=2 errors each.
4. Phase 2 (cont.): After the above step, at most one site will be discovered to
contain more than f=2 corrupted page copies. 2f combined signatures are
requested from a correct site for the error detection of this site.
Next the algorithm is described in more details.
Phase 1 tries to locate one or more correct sites, as well as discover a number of
sites which are correct and hence need not be considered in Phase 2. This is done
by partitioning the set of sites into groups of 2 sites each. The reason for comparing
sites is that by Observation 2, the comparison of 2 sites can discover correct sites
if both the sites are correct, and that a set of 2 sites is the smallest possible set of
sites to detect a correct file copy. More messaging is needed if signatures in groups
of more than 2 sites are compared. Suppose groups are of 3 sites, the number of
sets of signatures to be sent in total is d 2
3 Me, which is greater than d 1
2 Me for the
case with groups of size 2. 1 It will be seen in Section 6 that with this arrangement,
LOCATING CORRUPTIONS IN A REPLICATED FILE 15
ALGORITHM GF SIG A:
The followings are operations at site s i1 of G i .
Phase 2: Find corrupted page copies
(1) *.Let FG be the set of groups G j with message
(2) *.Let F be the number of groups in FG.
sites in this group are correct);
(5) If chosen by Protocol A, SEND the first f combined signatures to some sites
messages and SEND signatures according to requests.
Else
(8) There is a site sc which is correct and chosen by Protocol A for G i .
are incorrect)
If it is not true that
(The site is corrupted)
Compute a vector (e1;m ; :::; eN;m ) of at most minfN; f=2g
non-zero elements as a solution to the system of equations
(each site has - f=2 errors), then all corrupted pages are found
(20) Else at most one site sw has more than f=2 errors, sw has no solution in the above.
G is the number of corrupted page copies found so far.
exists and is in this group
Compute a vector (e1;w ; :::; eN;w ) with at most f non-zero elements
(34) as a solution to the system of equations
(38) *. ( Note: Cm is the set of corrupted pages in site sm .)
Figure 1b: Phase 2 of Algorithm GF SIG A
a minimum amount of combined signature transmission is achieved if no failures
occur, which is a desirable property given a relatively reliable system.
Phase 1 is where Assumption A leads to a significant gain in minimizing the
signature transmission compared to Consideration Z. With Consideration Z, in
order to locate a correct site, one must find a majority of sites whose first k combined
signatures are identical, where k is the number of possible errors at a site. In the
worst case one would have to collect the combined signatures from every site before
the majority is found. The number of signature transmissions is given by
With Assumption A, one can find a correct site by comparing 2 sites at a time,
and hence in Phase 1 of Algorithm GF SIG A, only M
transmissions
are necessary.
In Phase 1, for each group of 2 sites, a number of combined signatures are com-
pared. The maximum possible number of differing page copies between 2 sites is
given by f . Hence the first f pairs of combined signatures are compared. By Observation
2, if the values of the two sets of combined signatures
and are the same, then it means that both sites s i and s j have no
corruption. Otherwise, one or both contains corruption. it can be sured that at
least one group contains correct sites (see Lemma 2 in the following). The groups
inform each other whether they contain corruptions by sending messages "Correct"
or "Incorrect" to each other.
In Phase 2, for each group G i of FG, the site s i1 is active, and its operations are
shown in Figure 1b. In this phase, a Protocol A is applied which chooses a correct
site found in Phase 1 for each of the groups in FG. For example, there may be
unique site IDs for all sites and Protocol A may simply choose the correct site that
has the smallest ID. Alternatively, Protocol A may choose different correct sites
for different subsets of FG to minimize communication distances. Since this paper
considers only the transmission of messages in the performance analysis, the exact
detail in Protocol A is not of concern.
The first mission for s i1 is to receive the first f combined signatures from the
chosen correct site s c . There can be at most f corruptions at a site, therefore, by
Observation 2, these f combined signatures can be used to determined whether s i1
or s i2 are correct sites (Lines 10 to 12 of Algorithm GF SIG A).
The next step is to compute a solution with at most f=2 non zero elements to the
set of the first f signature equations for each corrupted site in G i (Lines (16)-(18)
of Algorithm GF SIG A). There are two possible cases,
LOCATING CORRUPTIONS IN A REPLICATED FILE 17
1. In the first case, each site has fewer than f=2 errors, since there are in total at
most f errors, then by Observation 3, there will be a unique solution for the
signature equations for each group in FG, and the solutions solve the problem.
2. In the second case, not every site has fewer than f=2 then there is at most one
site which has more than f=2 errors, and at this site, if it exists, there is no
solution with at most f=2 non-zero elements in the above computation. Let
this site be s w if it exists.
Continue with the steps for Case (2) above. For this case, corruptions at all sites
other than s w have been detected. For s w , more correct signatures will be necessary
for discovering the corrupted copies. Suppose G errors have been discovered at sites
other than s w , then the maximum number of errors at s w is bounded by f \Gamma G. Let
G)g. By Observations 1 and 3, the first f 00 combined signatures
of s w is compared with a correct site to solve the corresponding set of equation. If
s w is s i2 of group G i , since the first f of the combined signatures of both s w and a
correct site is known, site s i1 will ask for the next f + 1 to f 00 combined signatures
from s i2 . In this case, if s i1 is not a correct site, it would need to request for the
f to f 00 combined signatures from s c for the error detection. If s w is s i1 , then it
needs only collect the next (f +1) to f 00 combined signatures from a correct site s c .
Finally, a solution to the set of equations at Line (35) of Algorithm GF SIG A in
Figure 1b will give a solution for s w . Since this is the only site remaining unsolved,
error detection is now completed. The following lemma is thus shown:
computes the locations of corruption under the
given assumptions.
The following lemma establishes the correctness of Phase 1.
Phase 1 of Algorithm GF SIG A can always find a site s c , and s c
contains no corruption.
Proof: First note that at least one of the groups in GG contains 2 sites that
are correct. This is because of the assumption M - 2g none of the
groups in GG contains 2 sites that are correct, then g would be greater than M=2,
a contradiction to the assumption.
For the two correct sites, the combined signatures will be identical. Hence one
can always find a site s c . From the definition of sig k;i and sig k;j ,
The vector (S(P n;i has weight at most f . Since the combined signatures
sig k;i and sig k;j for agrees with each other,
. By
Assumption A, two sites that contain corrupted pages will have different signatures.
If the two sites have identical signatures, it means that the two sites are correct.
Hence one concludes that site s c has no corruption. 2
4.2. Algorithm GF SIG B: Considering bound on corruptions per site
The next proposed algorithm is called Algorithm GF SIG B. In this algorithm
a finer model than that of Algorithm GF SIG A is adopted. In particular, h, the
maximumnumber of corrupted page copies at a site at file comparison is considered.
Algorithm GF SIG B is shown in Figure 2. As in Algorithm GF SIG A, three
assumptions are made:
(1) Assumption A.
2g.
(3) the number of sites is a multiple of 2.
As in Algorithm GF SIG A, the third assumption is made only for the sake of
simplicity in the presentation. A brief outline of the algorithm is first given:
1. Phase 1: partition the set of sites into groups of size 2 each, find a correct site
by comparison of some combined signatures between the 2 sites in each group.
2. Phase 2: A set of groups FG will be found to contain corruptions. One site in
each such group will be active, it first receives some combined signatures from
a correct site found in Phase 1, in order to decide if itself is a correct site.
3. Phase 2 (cont.) The active site in each group determines if each site in the
group is correct, if the other site is not correct, more of its combined signatures
are requested if necessary. If both sites are incorrect, then more combined
signatures are received from a correct site.
4. Phase 2 (cont.) The active site solves a set of equations to identify the error
copies in each corrupted site in its group.
LOCATING CORRUPTIONS IN A REPLICATED FILE 19
ALGORITHM GF SIG B:
Given: a set of sites SS.
Preprocessing Partition SS into groups of size 2.
Let the partitioning be
The followings are operations at site s i1 of G i .
Phase 1: Find a correct site
Else message
(5) SEND( message i ) to s j1 of all other groups G j .
j1 of all other groups G j .
Figure 2a: Phase 1 of Algorithm GF SIG B
Next the algorithm is described in more details. Algorithm GF SIG B is shown
in

Figure

2. In the figure, most of the computations are based on the local view of
a site s i1 in a certain set of 2 sites. The lines (1)-(3) and (31)-(33) in Figure 2 are
where global computation or global consideration of some kind is made.
Phase 1 tries to locate one or more correct sites, as well as discover a number
of sites which are correct and hence need not be considered in Phase 2. As in
Algorithm GF SIG A, this is done by partitioning the set of sites into groups of
sites each. The reasons for this are the same as before. For each group in
the partition, a number of combined signatures are compared. At this stage, the
maximal number of corrupted page copies at any site is h - N is known. The
maximum possible number of differing page copies between 2 sites is given by
2hg. Hence the first f 0 pairs of combined signatures are compared.
Using the arguments in Algorithm GF SIG A, at least one correct site will be
discovered.
Phase 2 makes use of the combined signatures of the correct site discovered in
phase one to identify the corrupted pages in the corrupted sites. After Phase 1,
a set FG of groups of 2 sites is identified, where each such group has at least
one corrupted site (refer to Figure 2). Suppose there are F groups in FG, it
implies that at least F of the sites contain at least one corrupted page copy each.
ALGORITHM GF SIG B:
The followings are operations at site s i1 of G i .
Phase 2: Find corrupted page copies
(1) *. Let FG be the set of groups G j with message
(2) *.Let F be the number of groups in FG, i.e.
g.
sites in this group are correct);
If chosen by Protocol A, SEND(sig1;c ; :::sig f 00 ;c ) to some sites and Wait
for REQUEST messages and SEND signatures according to requests.
Else
There is a site sc which is correct and chosen by Protocol A.
are incorrect)
If it is not true that
Compute a vector (e1;m ; :::; eN;m ) of weight at most
1g as a solution to the system of equations
corresponds to S(Pi;m
is the set of corrupted page copies in site sm .)
Figure 2b: Phase 2 of Algorithm GF SIG B
LOCATING CORRUPTIONS IN A REPLICATED FILE 21
Then the maximal possible number of corrupted page copies at any site is given
by f 1g. In order to identify f 00 errors, from Observation 3, if
one needs to compare the first 2f 00 combined signatures with a correct
site. If 2f 00 ? N , from Observation 1, one needs to compare only the first N pairs
of combined signatures. Therefore, let f (Line (3) of Algorithm
GF SIG B). The values of f 00 and f 000 will help to determine the number of signature
transmission in the following steps.
As in Algorithm GF SIG A, Protocol A is applied to choose a correct site for each
of the groups in FG. At each group fs i1 ; s i2 g in FG, one site, s i1 , is active. The
first task for s i1 is to find out if itself is a correct site, because if so, fewer number
of combined signatures need to be received in a later stage. To do so, it receives
the first f 00 combined signatures from a correct site s c . It compares its own first
f 00 combined signatures with these (Line (11) of Algorithm GF SIG B). By Observation
2, if the two sets of combined signatures are identical, then s i1 is correct.
In this case, s i1 will act as the correct site s d in discovering the corruptions of s i2 ,
and it would not need any more messages from s c . Otherwise, s i1 is corrupted, in
which case the way to find out if s i2 is correct is similar (Line(13) of Algorithm
GF SIG B). If s i1 is corrupted but s i2 is correct, then it is better to let s i2 act as
the correct site for error detection, since possibly more combined signatures (the
first f 00 of them) are received from s i2 than from s c . If s i2 is incorrect, then s i2 will
send the (f 00 + 1)-th to f 000 -th combined signatures to s i1 for error detection (Lines
of Algorithm GF SIG B). If both s i1 and s i2 are found to be corrupted the
role of correct site s d is played by s c .
If s i2 (s c ) is chosen as the correct site, then the remaining signatures in the first
f 000 combined messages, if any, will be collected from s i2 (s c ) (Lines (18-19) and
Lines (22-23) of Algorithm GF SIG B).
Finally, or i2) is corrupted, the solution to
e n;m ff
is computed (Lines (27)-(29) of Algorithm GF SIG B).
There are two possible cases, and the solution in each case gives a correct answer:
1. if f 000 = N , then by Observation 1, the corrupted page copies can be found;
2. if f since the maximalnumber of corrupted pages in s m is f 00 , therefore,
by Observation 3, the corrupted page copies can also be found.
22 WAICHEE FU AND SIU-CHEUNG CHAU
4.3. Algorithm GF SIG C: Considering bound on number of corrupted sites
Given Assumption A, one can assume that M ? is the maximum
number of sites that contain corruptions. If M ? 2, then at least 2 sites are
correct, and the algorithm in [1] can be slightly modified to detect all corruptions
for this case: In finding a correct site, instead of finding a majority of sites that
agree with each other, find a set of 2 sites that agree with each other. In the
worst case, the resulting amount of messaging is the same as the original algorithm
but now a much greater number of possible errors can be tolerated. The resulting
algorithm is called Algorithm GF SIG C.
5. Performance Analysis
In this section, the performance of Algorithm GF SIG A and Algorithm GF SIG B
is analyzed. The performance among the two algorithms and Algorithm GF SIG
are also compared. Both proposed Algorithms are shown to perform better than Algorithm
GF SIG in that fewer number of signature transmissions is necessary. The
choice between Algorithm GF SIG A and Algorithm GF SIG B are also discussed.
5.1. Performance of Algorithm GF SIG A
In Phase 1 of Algorithm GF SIG A, the number of messages transmitted will be
\Sigma M\Upsilon
f .
In Phase 2, let F be the number of groups in FG. Consider the number of
messages required for a group G i of FG. More messages are required if site s i1 is
not a correct site.
1. The total number of combined signatures transmitted from s c for a RECEIVE
at Line (9) of Algorithm GF SIG A in Figure 1b is given by f , and at most F
sites would receive these messages. Since f is the maximum number of failures,
F is at most f .
2. In the worst case no error may be found at sites other than s k . The total
number of combined signatures transmitted from s c for a RECEIVE at Line
(32) of Algorithm GF SIG A in Figure 1b is bounded by minfN \Gamma f; fg, and
at most one site would receive these messages.
LOCATING CORRUPTIONS IN A REPLICATED FILE 23
3. The total number of combined signatures transmitted from s i2 for a RECEIVE
at Line (28) of Algorithm GF SIG A in Figure 1b is bounded by minfN \Gamma f; fg,
and at most one site would receive these messages.
Together with the consideration of the cases for N - f , the total number of combined
signature transmissions is bounded by
d
A tighter bound is to consider the value of F which is defined in the above. The
bound is
d
If there is no failure, then the number of combined signature transmissions is
given by
5.2. Performance of Algorithm GF SIG B
In Phase 1 of Algorithm GF SIG B the number of messages transmitted will be
2hg.
In Phase 2, let F be the number of groups in FG. Consider the number of
messages required for a group G i of FG. More messages are to be received if site
s i1 is not a correct site.
1. The total number of combined signatures transmitted from s c for a RECEIVE
at Line (10) of Algorithm GF SIG B in Figure 2b is given by f
would receive these messages.
2. Since g is the maximum number of failed sites, the number of groups in FG
with corrupted sites is bounded from the above by bg=2c. The total number
of combined signatures transmitted from s c for a RECEIVE at Line (23) of
Algorithm GF SIG B in Figure 2b is given by f g, and at most
would receive these messages. 2
3. The total number of combined signatures transmitted from s i2 for a RECEIVE
at Line (19) of Algorithm GF SIG B in Figure 2b is also given by f 000 , and at
most F sites would receive these messages.
The total number of combined signature transmissions for Lines (3) and (19) of
Algorithm GF SIG B is bounded by
2hg. The total number of combined signature transmissions
for Lines (10) and (23) in Algorithm GF SIG B is bounded by
bg=2cg.
To summarize, given that f
g, the number of combined signature transmissions for Algorithm
bounded by
If there is no failure, then the number of combined signature transmissions is
given by
5.3. Performance Comparisons: Cases of No Failure
For reliable systems, it is likely that no failure has occurred at most file comparisons.
Therefore first consider the cases of no failure.
Compare the performance of Algorithm GF SIG A and Algorithm GF SIG B
with the bounds achieved by [1]. Recall that the more efficient decentralized algorithm
in [1] is called Algorithm GF SIG. The maximum number of signature
transmission it requires is given by
LOCATING CORRUPTIONS IN A REPLICATED FILE 25
However, when it happens that none of the sites contains more than f=2 failures,
then the number of signature transmission is given by:
First consider the case where no error actually occurs. The number of signature
transmission required in Algorithm GF SIG A, Algorithm GF SIG B and Algorithm
GF SIG for different sets of parameters are plotted in Figure 3. The difference
between the number of signature transmission for the two algorithms is
shown in Figure 4. (In these figures, fl A
f) is denoted by Gamma(0A),
denoted by Gamma(0A), fi 0 (M; N; f) is denoted by Beta(0).)
When comparing fl A
Note that the minimum value
of fi 0 (M;N; f) occurs at the smallest possible value of f , namely 1, in which
case
fg. From Figure 4(a), the savings of Algorithm
GF SIG A on the message transmission approximately ranges from M
at
minfN; fg at 1c. It can be seen that the enhancement
in performance of Algorithm GF SIG A and Algorithm GF SIG B over Algorithm
GF SIG increases with the number of errors to be detected.
5.4. Cases with Failures
The maximumnumbers of signature transmission required for Algorithm GF SIG A
and Algorithm GF SIG B under different system parameters of N;M; f; g and F are
shown in Figure 5. The requirements of Algorithm GF SIG are also shown. In the
remaining figures, fi(M; N; f) is denoted by Beta(w), and fi 0 (M;N; f) is denoted
by Beta(0). fl A (M;N; f) and are denoted by Gamma(A) and
Gamma(B), respectively.
The value
for the case of no failure is a lower bound
on the value of From the figure, it is seen that the value of
furthest away from fl B
relatively unreliable
system, where the number of possible failing sites is almost half the number
of sites (Figure 5(a)). The difference becomes smaller as the number of possible
failing sites is decreased (Figure 5(c)).
5.4.1. Favourable Conditions for Algorithm GF SIG A. The previous performance
comparisons show that both Algorithm GF SIG A and Algorithm GF SIG B
have better performance than Algorithm GF SIG. Next the choice between Algo-
26 WAICHEE FU AND SIU-CHEUNG CHAU
(a) (b)
(c) (d)

Figure

3: Signature transmission of Algorithm GF SIG A, Algorithm GF SIG B
and GF SIG under no failure
LOCATING CORRUPTIONS IN A REPLICATED FILE 27
(a) (b)

Figure

4: Difference between Algorithm GF SIG A and GF SIG under no failure
rithm GF SIG A and Algorithm GF SIG B is examined. Algorithm GF SIG A
will be shown to be a good choice if the parameter of h is not considered. Figure 6
shows the performance of Algorithm GF SIG, Algorithm GF SIG A, and Algorithm
GF SIG B, without considering the parameters h and g, that is, h and g are set to
their greatest possible values, respectively. The values of fi(M; N; f), fl A (M; N; f),
are plotted for for each of
From the figures, if F is small compared to f , then Algorithm GF SIG A performs
better than Algorithm GF SIG in that the amount of messaging is less. These
diagrams show that Algorithm GF SIG AA is a better choice if the parameter of h
is not considered.
5.4.2. Favourable Condition for Algorithm GF SIG B: The parameter h. Figure
7 illustrates the significance of parameter h, the maximumnumber of corrupted page
copies at a site. If this is not known, h may be assumed to be minfN; fg. However,
it is not likely that all pages of a file are corrupted. In the figures, some reasonable
values of h, such as 10% of the total number of pages, are assumed. Compared with

Figure

5, the number of required signature transmission are reduced significantly.
Since only Algorithm GF SIG B takes advantages of h, it is the best choice if a
reasonable value of h is known.
28 WAICHEE FU AND SIU-CHEUNG CHAU
Beta(w)

Beta(w)
(a) (b)

Beta(w)

Beta(w)
(c) (d)

Figure

5: Number of signature transmissions for Algorithm GF SIG A, Algorithm
Algorithm GF SIG with failure
LOCATING CORRUPTIONS IN A REPLICATED FILE 29

Beta(w)

Beta(w)
(a) (b)

Beta(w)

Beta(w)
(c) (d)

Figure

Signature transmission of Algorithm GF SIG, Algorithm GF SIG A and
Algorithm GF SIG B with failure
Beta(w)
Beta(w)
(a) (b)
Beta(w)
Beta(w)
(c) (d)

Figure

7: Effects of reasonable values of h for Algorithm GF SIG B
LOCATING CORRUPTIONS IN A REPLICATED FILE 31
6. A Lower Bound and Optimality
It can be shown that Algorithm GF SIG A and Algorithm GF SIG B transmit
the minimal number of combined signatures for the case where no failure occurs.
Any failure that could have occurred must be detected. Therefore each site must
compare its combined signatures with some other site in order to determine if it
is correct. The minimal number of site comparisons is dM=2e. If less number of
comparison is made, then there must be at least one site which has not compared
with any other site.
Reasoning similar to that in [1, 2] is applied in our proof of optimality. When
sites compare to discover if either one or both is corrupted, if there can be at
most k failures in the 2 sites, then they must compare at least minfN; kg combined
signatures. Assume this is not true, i.e. the number of combined signatures t
compared is fewer than minfN; kg. If the signature size is b, then t combined
signatures can distinguish 2 bt different sets of page signatures. For a given pattern
in page signatures S(P minfN;kg+1 ); :::; S(PN ), there are 2 b minfN;kg different patterns
for the entire set of page signatures. Since t is less than minfN; kg, there are
two sets of page signatures
and
that agree on the last
pages but disagree in at least one page signature among the first
pages, such that the combined signatures of these two sets are identical in
the comparison. Hence there is no way to discover the difference if one site contains
the set of page signatures p and another site contains the set of page signatures p 0 .
Under the system model for Algorithm GF SIG B, the number of possible differing
copies of 2 sites is given by minfN; f; 2hg. Under the system model for
Algorithm GF SIG A, the number of possible differing copies of 2 sites is given by
minfN; fg. In practice, if comparison is made one by one, we may discover some
corruptions in the earlier comparisons and reduce this number of possible errors
for later comparisons. However, in the worse case, all the errors can occur at the
in the the last comparison, so that this number cannot be reduced for any of
the comparisons. Therefore, in the worst case, the number of combined signatures
needed to be transmitted is given by
\Sigma M\Upsilon minfN; f; 2hg (
\Sigma M\Upsilon minfN; fg). This is
achieved by Algorithm GF SIG B and GF SIG A when no corruption occurs (i.e.
the assumptions in Algorithm GF SIG B, the minimum number
of combined signature transmission in the case of no failure is given by
the assumptions in Algorithm GF SIG A, the minimum number
of combined signature transmission in the case of no failure is given by
7. Relaxing Assumption A
Assumption A states that the probability that 2 copies of the same page are corrupted
and that their signatures are identical is negligible. Now it is shown how this
assumption may be relaxed. Assumption A is replaced by the following assumption,
2:
Assumption C: the probability that any R corrupted copies of a page have identical
signatures is negligible.
Assumption C, for X ! R corrupted copies of a page, the error patterns
can be identical (the chance is not assumed to be negligible). Hence when there
are X sites showing identical signatures, it cannot be concluded that there is no
corruption. However, with R sites, if at least one copy is corrupted but not all
copies are corrupted, the differences in the signatures of the corrupted copies as
compared to those of the correct site(s) will be seen; if all R copies are corrupted,
at least one copy would have a corruption pattern that is different from some other
copy. Hence, when it is found that all signatures are identical in R copies, one can
conclude that all R copies are correct.
It may also be desirable to relax the second assumption of Algorithm GF SIG A
and Algorithm GF SIG B which states that M ? 2g. Note that this assumption
and Assumption A are actually related. With Assumption C, Phase 1 of Algorithm
GF SIG A and Algorithm GF SIG B may be modified as follows: Partition the set
of sites into groups of k(k - R) sites so that one leader site in each group gets to
know the necessary combined signatures of all sites in the group. Note that any
R sites which contain identical signatures will be correct sites. In order to prevent
such a set from appearing in a group of k sites, at least k must be
corrupted in the group. Therefore, the assumption M ? 2g can be replaced by
Rg. For
is an integer - 2. Using
larger values of k implies that more site failures can be tolerated, but it would also
increase the number of signature transmissions in cases where there is no corrupted
site.
LOCATING CORRUPTIONS IN A REPLICATED FILE 33
Assumption C, the value of g is bounded by
8. Summary and Conclusion
By making the realistic assumption that different sites are unlikely to contain corrupted
copies of a page of a replicated file with identical page signatures, three
algorithms are proposed for locating corruptions which have advantages over previous
methods. The first algorithm is based on a system model as in previous work,
and achieves better performance in terms of the number of signature transmission
than previous work. The second algorithm is based on a finer model in which the
maximum number of corrupted pages in each site is defined, and is shown to have
further enhancements in the amount of signature transmission. The third algorithm
allows more tolerance in data corruption compared to previous methods. The first
two algorithms are also shown to be optimal in terms of the number of signature
transmission in the case of no failure.
Notes
1. However, in this case of partitions of size 3, in order for at least one group to discover a correct
file copy, it is no longer required that M ? 2g, one need only require that M ? 3
g. There will
be more discussion about this in Section 7.
2. Note that the analysis can be refined by considering the number of groups in FG that contain 2
corrupted sites. Suppose this value is K. K is typically much smaller than F . This is because
the chance of having 2 corrupted sites in a group in FG equals the probability that a site
contains corruption, and for a reliable system this is small. If K is taken into consideration
in the analysis, better performance can be achieved. This is not considered for the sake of
simplicity.



--R

Efficient Detection of Corrupted Pages in a Replicated File 12th ACM Symposium on Principles on Distributed Computing.
Comparing multiple file copies with a primary copy using minimal communication.
An optimal strategy for comparing file copies
Exploiting symmetries for low-cost comparison of file copies
Theory and Practice of Error Control Codes.
Locating more corruptions in a Replicated File.

A parity structure for large remotely located replicated data files.
Reliable and efficient broadcast of files to a group of locally interconnected stations.
Efficient replicated remote file comparison.

--TR

--CTR
Changsik Park , John J. Metzner, Efficient Location of Discrepancies in Multiple Replicated Large Files, IEEE Transactions on Parallel and Distributed Systems, v.13 n.6, p.597-610, June 2002
performance analysis;message transmission;signatures;file comparison;coding theory;fault tolerance;replicated file