Deterministic Voting in Distributed Systems Using Error-Correcting Codes.
AbstractDistributed voting is an important problem in reliable computing. In an N Modular Redundant (NMR) system, the N computational modules execute identical tasks and they need to periodically vote on their current states. In this paper, we propose a deterministic majority voting algorithm for NMR systems. Our voting algorithm uses error-correcting codes to drastically reduce the average case communication complexity. In particular, we show that the efficiency of our voting algorithm can be improved by choosing the parameters of the error-correcting code to match the probability of the computational faults. For example, consider an NMR system with 31 modules, each with a state of m bits, where each module has an independent computational error probability of 103. In this NMR system, our algorithm can reduce the average case communication complexity to approximately 1.0825m compared with the communication complexity of 31m of the naive algorithm in which every module broadcasts its local result to all other modules. We have also implemented the voting algorithm over a network of workstations. The experimental performance results match well the theoretical predictions.
Introduction
Distributed voting is an important problem in the creation of fault-tolerant computing systems,
e.g., it can be used to keep distributed data consistent, to provide mutual exclusion in distributed
systems. In an N Modular Redundant (NMR) system, when the N computational modules
execute identical tasks, they need to be synchronized periodically by voting on the current
computation state (or result, and they will be used interchangeably hereafter), and then all
modules set their current computation state to the majority one. If there is no majority result,
then other computations are needed, e.g., all modules recompute from the previous result. This
technique is also an essential tool for task-duplication-based checkpointing [12]. In distributed
storage systems, voting can also used to keep replicated data consistent.
Many aspects of voting algorithms have been studied, e.g., data approximation, reconfigurable
voting and dynamic modification of vote weights, metadata-based dynamic voting[3][5][9]. In
this paper, we focus on the communication complexity of the voting problem. Several voting
algorithms have been proposed to reduce the communication complexity [4][7]. These algorithms
are nondeterministic because they perform voting on signatures of local computation results.
Recently, Noubir et. al. [8] proposed a majority voting scheme based on error-control codes:
each module first encodes its local result into a codeword of a designed error-detecting code
and sends part of the codeword. By using the error-detecting code, discrepancies of the local
results can be detected with some probability, and then by a retransmission of full local results,
a majority voting decision can be made. Though the scheme drastically reduces the average case
communication complexity, it can still fail to detect some discrepancies of the local results and
might reach a false voting result, i.e., the algorithm is still a probabilistic one. In addition, this
scheme is only using the error detecting capabilities of codes. As this paper will show, in general,
using only error-detecting codes ( EDC ) does not help to reduce communication complexity of
a deterministic voting algorithm. Though they have been used in many applications such as
reliable distributed data replication [1], error-correcting codes ( ECC ) have not been applied to
the voting problem.
For many applications[12], deterministic voting schemes are needed to provide more accurate
voting results. In this paper, we propose a novel deterministic voting scheme that uses error-
correcting/detecting codes. The voting scheme generalizes known simple deterministic voting
algorithms. Our main contributions related to the voting scheme include: (i) using the correcting
in addition to the detecting capability of codes ( only the detection was used in known schemes )
to drastically reduce the chances of retransmission of the whole local result of each node thus the
communication complexity of the voting, (ii) a proof that our scheme provably reaches the same
voting result as the naive voting algorithm in which every module broadcasts its local result to
all other modules, and (iii) the tuning of the scheme for optimal average case communication
complexity by choosing the parameters of the error-correcting/detecting code, thus making the
voting scheme adaptive to various application environments with different error rates.
The paper is organized as follows: in Section 2, we describe the majority voting problem in
NMR systems. Our voting algorithm together with its correctness proof are described in Section
3. Section 4 analyzes both the worst case and the average case communication complexity of
the algorithm. Section 5 presents experimental results of performances of the proposed voting
algorithm, as well as two other simple voting algorithms for comparison. Section 6 concludes the
paper.
2 The Problem Definition
In this section, we define the model of the NMR system and its communication complexity. Then
we address the voting problem in terms of the communication complexity.
2.1 NMR System Model
An NMR system consists of N computational modules which are connected via a communication
medium. For a given computational task, each module executes a same set of instructions
with independent computational error probability p. The communication medium could be a
bus, a shared memory, a point-to-point network or a broadcast network. Here we consider the
communication medium as a reliable broadcast network, i.e., each module can send its computation
result to all other modules with only one error-free communication operation. The system
evolution is considered to be synchronous, i.e., the voting process is round-based.
2.2 Communication Complexity
The communication complexity of a task in an NMR system is defined as the total number of
bits that are sent through the communication medium in the whole execution procedure of the
task. In a broadcast network, let m ij be the number of the bits that the ith module sends
at the jth round of the execution of a task, then the communication complexity of the task is
is the number of the modules in the system, and K is the number of
rounds needed to complete the task.
2.3 The Voting Problem
Now consider the voting function in an NMR system. In an NMR system, in order to get a
final result for a given task, after each module completes its own computation separately, it
needs to be synchronized with other modules by voting on the result. Denote X i as the local
computational result of the ith module, the majority function is defined as follows:
OE otherwise
where in general, N is an odd natural number, and OE is any predefined value different from all
possible computing results.
Example 1 If
changes to 0010, and other X 0
then
The result of voting in an NMR system is that each module gets Majority(X
final result , where X is the local computation result of the ith module.
One obvious algorithm for the voting problem is that after each module computes the task,
it broadcasts its own result to all the other modules. When a module receives all other modules'
results, it simply performs the majority voting locally to get the result. The algorithm can be
described as follows:
Algorithm 1 Send-All Voting
For Module
Wait Until Receive all
This algorithm is simple: each module only needs one communication (i.e., broadcast) oper-
ation, but apparently its communication complexity is too high. If the result for the task has
bits, then the communication complexity of the algorithm is Nm bits. In most cases, the
probability of a module to have a computational error is rather low, namely at most times all
modules shall have the same result, thus each module only needs to broadcast part of its result.
If all the results are identical, then each module shall agree with that result. If not, then modules
can use Algorithm 1. Namely, we can get another simple improved voting algorithm as follows:
Algorithm 2 Simple Send-Part Voting
For Module
Partition the local result X i into N symbols: X
Wait Until Receive all
If
Else
Wait Until Receive all
In the above algorithm, * is a concatenation operation of strings, e.g.,
is an equality evaluation:
FALSE otherwise
Some padding may be needed if the local result is not an exact multiple of N. The following
example demonstrates a rough comparison of the two algorithms.
round of communication
is needed, and in total 25 bits are transmitted. On the other hand, with Algorithm
broadcast 0, and
is the majority voting result. In this case, 2 rounds of communication
are done, and 10 bits ( 5 bits for X and 5 bits for F ) are transmitted.
results in and the Else part of the algorithm
is executed, finally the majority voting result is obtained by voting on all the X i 's, i.e.,
rounds of communication are needed, and in total,
bits ( 25 bits for X i 's and 5 bits for F) are transmitted. 2
From the above example, it can be observed:
1. Algorithm 1 always requires only 1 round of communication, and Algorithm 2 requires 2
or 3 rounds of communication;
2. The Else part of Algorithm 2 is actually Algorithm
3. The communication complexity of Algorithm 1 is always Nm, but the communication
complexity of Algorithm 2 may be m+N or Nm+N , depending on the X i 's;
4. In Algorithm 2, by broadcasting and voting on the voting flags, i.e., F i 's, the chance for
getting a false voting result is eliminated.
If the Else part of Algorithm 2, i.e., Algorithm 1, is not executed too often, then the communication
complexity can be reduced to m+N from Nm, and in most cases, m AE N , thus
m. So the key idea used to reduce the communication complexity is to reduce the
chance to execute Algorithm 1. In most computing environments, each module has low computational
error probability p, thus most probably all modules either (1) get the same result or (2)
only few of them get different results from others. In case (1), Algorithm 2 has low communication
complexity, but in case (2), Algorithm 1 is actually used and the communication complexity
is high (i.e., Nm+N) , but if we can detect and correct these discrepancies of the minor modules'
results, then the Else part of the Algorithm 2 does not need to be executed, the communication
complexity can still be low. This detecting and correcting capability can be achieved by using
error-correcting codes.
3 The Solution Based on Error-Correcting Codes
Error-correcting codes ( ECC ) can be used in the voting problem to reduce the communication
complexity. The basic idea is that instead of broadcasting its own computation result X i di-
rectly, P i , the ith module, first encodes its result X i into a codeword Y i of some code, and then
broadcasts one symbol of the codeword to all other modules. After receiving all other symbols of
the codeword, it reassembles them into a vector again. If all modules have the same result, i.e.,
all are equal, then the received vector is the codeword of the result, thus it can be decoded
to the result again. If the majority result exists, i.e., Majority(X OE, and there are t
c) modules whose results are different from the majority result X, then the symbols from
all these modules can be regarded as error symbols with respect to the majority result. As long
as the code is designed to correct up to t errors, these error symbols can be corrected to get the
codeword corresponding to the majority result, thus Algorithm 1 does not need to be executed.
When the code length is less than Nm, the communication complexity is reduced compared to
Algorithm 1. On the other hand, if only error-detecting codes are used, once error results are
detected, Algorithm 1 still needs to be executed, and thus increases the whole communication
complexity of the voting. Thus error-correcting codes are preferable to error-detecting codes
for voting. By properly choosing the error-correcting codes, the communication complexity can
always be lowered than that of Algorithm 1.
But it is possible that the majority result does not exist, i.e., Majority(X
the vector that each module gets can still be decoded to a result. As observed from the above
example, introduction of the voting flags can avoid this false result.
3.1 A Voting Algorithm with ECC
With a properly designed error-correcting code which can detect up to d and correct up to t
error voting algorithm using this code is as follows:
Algorithm 3 ECC Voting
For Module
Wait Until Receive all Y
If Y is undecodable
Execute Algorithm
Else
If
Else
Execute Algorithm
Notice that to execute Algorithm 1, each module P i does not need to send its whole result
It only needs to send additional of its codeword Y i . Since the code is
designed to detect up to d and correct up to t symbols, it can correct up to d
the unsent d+t symbols of Y i can be regarded as erasures and recovered, hence the original X i
can be decoded from Y i .
To see the algorithm more clearly, the flow chart of the algorithm is given in Fig. 1, and the
following example shows how the algorithm works.
Example 3 There are 5 modules in an NMR system, and the task result has 6 bits, i.e.,
Here the EVENODD code [2] is used which divides 6-bit information into 3 symbols
the reassembled vector Y
into N symbols
Broadcast(Y (i)), wait until get
Execute "Send-All Voting"
Majority(F , . , F

Figure

1: Flow Chart of Algorithm 3
and encode information symbols into a 5-symbol codeword. This code can correct 1 error symbol,
Now if then with the EVENODD code,
after each module broadcasts 1 symbol
(i.e., 2 bits) of the codewords, the reassembled vector is Y=0000000001. Since Y has only 1 error
symbol, it can be decoded into X=000000. From the flow chart of the algorithm, we can see that
is the majority
voting result.
In this case, there are 2 rounds of communication, and the communication complexity is 15
bits. As a comparison, algorithm 1 needs 1 round of communication, and its communication
complexity is 30 bits; on the other hand, algorithm needs 3 rounds of communication, and the
communication complexity in this case is 35 bits. In this example, the EVENODD code is used,
but actually the code itself does not affect the communication complexity as long as it has same
properties as the EVENODD code, namely, an MDS code with
From the flow chart of the algorithm, the introduction of voting on F i 's ensures not to reach a
false voting result, and going to the Send-All Voting in worst case guarantees not to fail to reach
the majority result if it exists. Thus the algorithm can give a correct majority voting result. A
rigorous correctness proof of the algorithm is as follows.
3.2 Correctness of the Algorithm
Theorem 1 Algorithm 3 gives Majority(X set of local computational
results
Proof: From the flow chart of the algorithm, it is easy to see that the algorithm terminates in
the following two cases:
1. Executing the Send-All Voting algorithm: the correct majority voting result is certainly
reached;
2. Returning a X: in this case, since Majority(F
are equal to X, X is the majority result. 2
To see how the algorithm works with various cases of the local results X i 's
give two stronger observations about the algorithm, which also help to analyze the communication
complexity of the algorithm.
outputs OE, i.e., Algorithm 3
never gives a false voting result.
Proof: It is easy to see from the flow chart that after the first round of communication, each
module gets a same vote vector Y . According to the decodability of Y, there are two cases:
1. If Y is undecodable, then the Send-All Voting algorithm is executed, and the output will
be OE;
2. If Y is decodable, the decoded result X now can be used as a reference result. But since
there does not exist a majority voting result, majority of the X i 's are not equal to the X, i.e.,
so the Send-All Voting algorithm is executed, and the output
again will be OE. 2
output is exactly the
X, i.e., Algorithm 3 will not miss the majority voting result.
Proof: Suppose there are e modules whose local results are different from the majority result
X, then e -
1. If e - t, then there are e error symbols in the vote vector Y with respect to the corresponding
codeword of the majority result X, so Y can be correctly decoded into X, and majority of
are equal to X, i.e., majority of F i 's is 1, hence the correct majority result X is outputted.
2. If e ? t, then Y is either undecodable or incorrectly decoded into another X 0 , where X 0 6=
X. In either case, the Send-All voting algorithm is executed and the correct majority result X is
reached. 2
3.3 Proper Code Design
In order to reduce the communication complexity, we need an error-correcting code which can be
used in practice for Algorithm 3. Consider a block code with length M. Because of the symmetry
among the N modules, M needs to be a multiple of N, i.e., each codeword consists of N symbols,
and each symbol has k bits, thus Nk. If the minimum distance of the code is d min , then
2 c, since the code should be able to detect up to d error
symbols and correct up to t error symbols[6]. Recall that the final voting result has m bits, the
code to design is a (Nk; m; (d
To get the smallest value for k, by the Singleton Bound in coding theory[6],
we get
(2)
Equality holds for all MDS Codes[6].
So given a designed (d; t), the smallest value for k is d m
e. If m
is an integer, all MDS
Codes can achieve this lower bound of k. One class of commonly used MDS codes for arbitrary
distances is the Reed-Solomon code[6]. If m
is not an integer, then any (Nk; m; (d+ t)k +1)
block code can be used, where
e, one of the examples is the BCH code, which can
also have arbitrary distances[6]. The exact parameters of (k; d; t) can be obtained by shortening
setting some information symbols to zeros ) or puncturing ( deleting some parity symbols
Notice that
In most applications, N - m, thus the N
bits of F i 's can be neglected, and k is approximately the number of the bits that each module
needs to send to get final voting result, so the communication complexity of Algorithm 3 is always
lower than that of Algorithm 1.
In this paper, only the communication complexity of voting is considered, since in many
systems, computations for encoding and decoding on individual nodes are much faster than
reliable communications among these nodes, which need rather complicated data management
in different communication stacks, retransmission of packets between distributed nodes when
packet loss happens. However, in real applications, design of proper codes should also make the
encoding and decoding of the codes as computationally efficient as possible. When the distances
of codes are relatively small, which is the case for most applications when the error probability p
is relatively low, more computation-efficient MDS codes exist, such as codes in [2], [10] and [11],
all of which require only bitwise exclusive OR operations.
Communication Complexity Analysis
4.1 Main Results
From the flow chart of Algorithm 3, we can see if the algorithm terminates in branch 1, i.e., the
algorithm gets a majority result, then the communication complexity is N(k+1); if it terminates
in branch 2, then the communication complexity is N(m+1); finally if the algorithm terminates in
branch 3, the communication complexity is Nm, thus the worst case communication complexity
Cw is N(m
Denote C a as the average case communication complexity of Algorithm 3, and define the
average reduction factor ff as the ratio of C a over the communication complexity of the Send-All
Voting algorithm (i.e., Nm), namely
Nm
, then the following theorem gives the relation
between ff and the parameters of an NMR system and the corresponding code:
Theorem 2 For an NMR system with N modules each of which executes an identical task of m-bit
result and has computational error with probability p independent of other modules' activities,
if Algorithm 3 uses an ECC which can detect up to d and correct up to t error symbols, and
holds for the average reduction factor of Algorithm 3:
where
Proof: To get the average case communication complexity C a of Algorithm 3, we need to analyze
the probability P i of the algorithm terminating in the branch i, 3. First assume that if
a module has an erroneous result X i , then it contributes an error symbol to the voting vector
Y . From the proof of Observation 2, if the algorithm terminates in the branch 1, then at most
modules have computational errors, thus the probability of this event is exactly P 1 . The event
that the algorithm reaches the branch 2 corresponds to the decoder error event of a code with
minimum distance of d+t+1, thus [6]
b d+t
where fA i g is the weight distribution of the code being used, and P ik is the probability that a
received vector Y is exactly Hamming distance k from a weight-i (binary) codeword of the code.
More precisely,
!/
If the weight distribution of the code is unknown, P 2 can be approximately bounded by
b d+t
Since the second term in the right side of the inequality above is just the probability of event
that correctable errors happen. Finally P 3 is the probability of the decoder failure event,
Now notice the fact that a module has an erroneous result can also contribute a correct symbol
to the voting vector, the average case communication complexity is
and the average reduction factor is
Notice that
e, and we get the result of ff as in Eq. (3). 2
Remarks on the theorem : From Eq. (3), we can see the relation between the average
reduction factor ff and each branch of Algorithm 3. The first term relates to the first branch
whose reduction factor is k
, or 1
when m is large enough relative to N , the round-off error
of partition can be neglected, and P 1 is the probability of that branch. One would expect this
term to be the dominant one for the ff, since with a properly designed code tuned to the system,
the algorithm is supposed to terminate at Branch 1 in most cases. The second term is simply the
probability that the algorithm terminates at either Branch 2 or Branch 3, where the reduction
factor is 1 ( i.e., there is no communication reduction since all the local results are transmitted
considering the 1 bit for F i 's in Branch 2. The last term is due to the 1 bit for voting
on F i 's. When the local result size is large enough, i.e., m AE 1, this 1 bit can be neglected in
our model. Thus in most applications, the result in the theorem can be simplified as
since the assumption that m AE 1 is quite reasonable.
From the above theorem and its proof, it can be seen that for a given NMR system (i.e., N
and p), P 1 is only a function of t, so if t is chosen, from Eq. (3) or Eq. (11) it is easy to see that
ff monotonically decreases as d decreases. Recall that 0 - t - d, thus for a chosen t, setting
can make ff minimum when m AE 1. Even though it is not straight forward to get a closed
form of t which minimize ff, it is almost trivial to get such an optimal t by numerical calculation.
Fig. 2 shows relations between ff and (t; p; N ). Fig. 2a and Fig. 2b show how ff (using Eq.
change with t for some setup of (N; p) when t. It is easy to see that for small p and
reasonable N , a small t (e.g., t - 2, for N - 51 with can achieve minimal ff. These
results show that for a quite good NMR system (e.g., p - 0:01), only by putting a small amount
of redundancy of the local results and apply error-correcting codes on them, the communication
complexity of the majority voting can be drastically reduced. Since the majority result is of m
bits, and each module shall get an identical result after the voting, the communication complexity
of the voting problem is at least m bits, thus ff - 1
is the lower bound of ff. Fig. 2c
shows the closeness of the theoretical lower bound of ff and the minimum ff that Algorithm 3
can achieve for some setup of NMR systems.
4.2 More Observations
From the above results, we can see that the communication complexity of the Algorithm 3 is
determined by the code design parameters (d; t). In an NMR system with N modules, we only
need to consider the case where at most b N
modules have different local results with the majority
(a) ff vs. t for different p with fixed vs. t for different N with fixed
p=.1
alpha
alpha
lower bound

Figure

2: Relations between ff and (t; p; N)
result, thus the only constraints of (d,t) is
2 c. For some specific values of (d,t),
the algorithm reduces to the following cases:
1. When repetition code is used, the algorithm becomes Algorithm 1.
Since a repetition code is always the worst code in terms of redundancy, it should always be
avoided for reducing the communication complexity of voting. On the other hand, when d=t=0:
the algorithm becomes Algorithm 2, and from Fig. 2, we can see that for a small enough p and
reasonable N , e.g., actually is a best solution of the majority
voting problem in terms of the communication complexity. Besides, Algorithm 2 has low computational
complexity since it does not need any complex encoding and decoding operations. Thus
the ECC voting algorithm is a generalized voting algorithm, and its communication complexity
is determined by the code chosen.
2. then the code only has detecting capability, but if m AE N , then from the analysis
above, increasing d actually makes ff increasing. Thus it is not good to put some redundancy
to the local results only for detecting capability when m AE N , i.e., using only EDC ( error
detecting code ) does not help to reduce the communication complexity of voting. The scheme
proposed in [8] is in this class with
3.
2 c: as analyzed above, in general, it is not good to have d ? t in terms of ff,
since increase of d will increase ff when t is fixed. But in this case, Algorithm 3 has a special
property: branch 2 of the algorithm can directly come to declare there is no majority result
without executing the Send-All Voting algorithm, simply because the code now can detect up
to b Nc errors, so if there was a majority result, then Y (refer to the Fig. 1) can have at
most b N
erroneous modules, and since Y is decodable, the majority of the local results should
agree with the decoded result X, i.e., Majority(F contradicts with the
actual there is no majority result. By setting d to b N
3 always has 2 rounds of communication and the worst case communication complexity is thus
Nm instead of N(m + 1) for the general case, and this achieves the lower bound of the worst
case communication complexity of the distributed majority voting problem [8].
5 Experimental Results
In this section, we show some experimental results of the three voting algorithms discussed above.
The experiments are performed over a cluster of Intel Pentium/Linux-2.0.7 nodes connected via a
100 Mbps Ethernet. Reliable communication is implemented by a simple improved UDP scheme:
whenever there is a packet loss, the voting operation is considered as a failure and redone from
beginning. By choosing suitable packet size, there is virtually no packet loss using UDP.
To examine real performances of the above three voting algorithms, N nodes vote on a result
of length m using all the three voting algorithms. For the ECC Voting algorithm, an EVENODD
Code is used, which corrects 1 error symbol, i.e., for the ECC Voting algorithm. Random
errors are added to local computing results with a preassigned error probability p, independent
of results at other nodes in the NMR system. Performances are evaluated by two parameters
for each algorithm: the total time to complete the voting operation T and the communication
time for the voting operation C. Among all the local T 's and C's, the maximum T and C are
chosen to be the T and C of the whole NMR system, since if the voting operation is considered
as a collective operation, the system's performance is determined by the worst local performance
in the system. For each set of the NMR system parameters ( N nodes and error probability
voting operation is done 200 times and random computation errors in each run are
independent of those in other runs, and the arithmetic average of C's and T 's are regarded as
the performance parameters for the tested NMR system.
Experimental results are shown in figures 3 through 5. Fig. 3 compares the experimental
average reduction factors of the voting algorithms with the theoretical results as analyzed in
the previous section, when they are applied in an NMR system of 5 nodes. Fig. 4 shows the
performances ( T and C ) of the voting algorithms. Detailed communication patterns of the
voting algorithms are shown in Fig. 5 to provide some deeper insight into the voting algorithms.
Fig. 3a and Fig. 3b show the experimental average reduction factors of the voting communication
for the Simple Send-Part Voting algorithm and the ECC Voting algorithm.
Fig. 3a and Fig. 3b also show the theoretical average reduction factors of the algorithm 2 and 3
as computed from the Eq. (11). Notice that the average communication time reduction factors ff
of both algorithm 2 and algorithm 3 are below 1, and as the computing result size increases, the
reduction factor approaches the theoretical bound, with the exception of the smallest computing
result size of 1 Kbyte.
Fig. 4 shows the performances of each voting algorithm applied in an NMR system of 5
nodes. Fig. 4ab show the total voting time T and Fig. 4cd show the communication time
C for voting. The only different parameter of the NMR systems related to the figures a and
symmetrically c and d ) is the error probability p: in the figures a and c, while
in the figures b and d. It is easy to see from the figures that for the voting algorithm 1
Voting ), T and C are the same, since besides communication, there is no additional
local computation. Fig. 4ab show that the algorithm 2 ( Simple Send-Part Voting ) and 3 ( ECC
Voting ) perform better than the algorithm 1 ( Send-All Voting ) in terms of the total voting
time T . On the other hand, Fig. 4cd show, in terms of C, i.e., the communication complexity,
the ECC Voting algorithm is better than the Simple Send-Part Voting algorithm when the error
(a) error probability
computing result size m ( Kbyte )
average
reduction
factor
a
(b) error probability
computing result size m ( Kbtye )
average
reduction
factor
a

Figure

3: Average Reduction Factors
(C(i) is the experimental average reduction factor of communication time for voting using algorithm i, and
ff(i) is the theoretical bound of the average communication reduction factor using algorithm i,
probability is relatively large ( Fig. 4c ) and worse than the Simple Send-Part Voting algorithm
when the error probability is relatively small ( Fig. 4d ), which is consistent with the analysis
results in the previous section.
In the analysis in the previous section, the size of local computing result m does not show
up as a variable in the average reduction factor function ff, since the communication complexity
is only considered as proportional to the size of the messages that need to be broadcasted. But
practically, communication time is not proportional to the message size, since startup time of
communication also needs to be included. More specially, in the Ethernet environment, since
the maximum packet size of each physical send ( broadcast ) operation is also limited by the
physical ethernet, communication completion time becomes a more complicated function of the
message size. Thus from the experimental results, it can be seen that for a computing result
of small size, e.g., 1 Kbyte, the Send-All Voting algorithm actually performs best in terms of
both C and T , since the startup time dominates the performance of communication. Also, the
communication time for broadcasting the 1-bit voting flags cannot be neglected as analyzed in
the previous section, particularly for a small size computing result. This can also be seen from
the detailed voting communication time pattern in Fig. 5ab: round 2 of the communication is
for the 1-bit voting flag, even though it finishes in much more shorter time than round 1, but is
still not negligibly small. This explains the fact that for small size computing results, the average
communication time reduction factors of algorithm 2 and algorithm 3 are quite apart from their
theoretical bound.
Further examination of the detailed communication time pattern of voting provides a deeper
insight into algorithm 3. From Fig. 5cd, it is easy to see that in the first round of communication,
algorithm 2 needs less time than algorithm 3 since the size of the message to be broadcasted is
smaller for algorithm 2. Besides, the first round of communication time does not vary as the error
probability p varies for the both algorithms. The real difference between the two algorithms lies
in the third round of communication. From Fig. 5c, this time is small for the both algorithms
since the error probability p is small ( 0.01 ). But as the error probability p increases to 0.1,
as shown in Fig. 5d, for algorithm 2, this time also increases to be bigger than the first round
time, since it has no error-correcting capability and once full message needs to be broadcasted,
its size is much bigger than in the first round. On the other hand, for algorithm 3, though it
also increases, the communication time for the third round is still much smaller than in the
first round, this comes from the error-correcting codes that algorithm 3 uses, since the code can
correct errors at one computing node, which is the most frequent error pattern that happens.
Thus even though the error probability is high, in most cases, the most expensive third round of
communication can still be avoided, and algorithm 3 performs better ( in terms of communication
complexity or time ) than algorithm 2 in high error probability systems, just as the predicted
analysis in the previous section.
6 Conclusions
We have proposed a deterministic distributed voting algorithm using error-correcting codes to
reduce the communication complexity of the voting problem in NMR systems. We also have given
a detailed theoretical analysis of the algorithm. By choosing the design parameters of the error-correcting
code, i.e., (d; t), the algorithm can achieve a low communication complexity which is
quite close to its theoretical lower bound. We have also implemented the voting algorithm over
a network of workstations, and the experimental performance results match well the theoretical
analysis. The algorithm proposed here needs 2 or 3 rounds of communication. It is left as an
open problem whether there is an algorithm for the distributed majority voting problem with its
average case communication complexity less than Nm using only 1 round of communication.



--R

"An Optimal Strategy for Computing File Copies"
"EVENODD: An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures"
"Voting Using Predispositions"
"Fault-Masking with Reduced Redundant Communication"
"Voting Without Version Numbers,"
The Theory of Error Correcting Codes
"Parallel Data Compression for Fault Tolerance"
"Using Codes to Reduce the communication Complexity of Voting in NMR Systems"
"Voting Algorithms"
"X-Code: MDS Array Codes with Optimal Encoding"

"Checkpointing in Parallel and Distributed Systems"
--TR
MDS code;error-correcting codes;NMR system;majority voting;communication complexity