Dynamic Grid Quorum: A Novel Approach for Minimizing Power Consumption
without Data Migration in Grid Quorums
Munetoshi Ishikawa, Koji Hasebe, Akiyoshi Sugiki, and Kazuhiko Kato
Graduate School of Systems and Information Engineering
University of Tsukuba
1-1-1 Tennodai, Tsukuba, Ibaraki 305–8573, Japan
munetoshi@osss. cs. tsukuba. ac. jp, hasebe@iit. tsukuba. ac. jp, {sugiki, kato}@cs. tsukuba. ac. jp

Abstract
In this paper, we present the dynamic grid quorum, atechnique for reducing the power consumption of largescale storage systems. The key idea is to skew the workload
towards a small number of quorums by means of anovel optimization algorithm. Moreover, this system allows
reconfiguration by exchanging nodes without any data
migration so as to reallocate high-capacity nodes to busier
quorums. We demonstrate that the dynamic grid quorum
saves, on average, 6-12% energy when compared with thestatic configurations.

1. Introduction
Service-oriented computing is a key paradigm in achieving the long-awaited, richer environments in computerscience. To achieve such platforms for large-scale businesscomputing systems, reliable, available, and cost-effective
data management is required.
The use of quorum systems is a promising approach
for achieving reliable data management in such platforms.
Compared with the traditional read-one write-all technique,the quorum approach allows flexibility in storage configuration and decentralized management for consistency control. Since the first quorum paper [7] was presented, muchresearch has focused on investigating the possibilities ofquorum systems. These studies are wide-ranging, fromdesired configurations in quorum systems [11], [1], [3],[12] to performance optimization methods that minimize
the communication delay [6], [15], [10]. On the other
hand, little attention has been paid to reducing power
consumption in quorum systems, which is necessary interms of green computing that has recently become ofprime interest to practitioners.

In this paper, we present the dynamic grid quorum, atechnique for reducing storage power consumption. As its
name implies, our approach is based on a grid quorum[3], but the key idea of our approach is to skew the
workload towards a small number of quorums. This canbe realized by our optimization algorithm for strategy(probability distribution over the quorums, determining
which quorum is selected for each read/write request).
Moreover, the dynamic grid quorum provides reconfiguration by exchanging nodes without any data migration.
Although the node exchange idea is used from the study
on tree-based quorums [5], much of the work had to beadapted for grid quorums. A major difference between gridand tree quorums is that nodes are naturally exchangeable
in tree-based quorums, whereas this is not the case ingrids. Since we also consider heterogeneity in nodes, thisreconfiguration method allows high-capacity nodes to beallocated to busier quorums so as to reduce the number ofactive nodes. Thus, our dynamic grid quorum can adapt
continuously to any environment, from read-intensive towrite-intensive workloads.
To evaluate the effectiveness of the proposed dynamic
grid quorum, we compared our approach with two static
read-optimized and write-optimized grid configurations.
From the simulations, we observed that our dynamic grid
quorum saved, on average, 6-12% energy compared withthe static configurations when the intensity of the total
workload was changed.
Related work. There have been a number of attempts to
reduce storage power consumption. A commonly-observed
feature in many of these techniques is that they adopt
the approach of skewing the load, which is also used inthis paper. In MAID [4] and PDC [13], popular data areconcentrated on specific disks. In DIV [14], original andredundant data are separated onto different disks, thereby
allowing read/write requests to be concentrated on thedisks with original data. In RIMAC [18], eRAID [16], andEERAID [9], a data access on a disk in standby mode istransformed into accesses on active disks or caches, andthen the required data are reconstructed from the parities
obtained during these accesses. In Hibernator [19] andPARAID [17], data are collected or spread to adapt tochanges in operational loads.
Paper organization. Sections 2 and 3 introduce the dynamic grid quorum and its power consumption model,
respectively. Section 4 gives the definition of our reconfiguration. Section 5 introduces the algorithm and provesthat it minimizes the power consumption of the dynamic
grid quorum. Section 6 presents the simulation results.
Finally, Section 7 concludes the paper and discusses future
research.

2. System Description
Our proposed system is based on the grid protocol [3],which is a special kind of write-read coterie [8], in which
the nodes are allocated in a rectangular grid. A write-readcoterie C is a pair hCW , CR i of collections of node groups,
called quorums, where CW and CR represent write quorums
and read quorums, respectively. Throughout this paper, we
fix the underlying set of nodes U = {ui,j | 1 ≤ i ≤ n∧1 ≤j ≤ m}, where each node is allocated in a grid with ncolumns and m rows. For readability, we use the following
notations. ui,j is used to denote a node at the intersectionof the i-th column (from the left) with the j-th row (fromthe bottom). This point is also referred to using the notation(i, j). Coli and Rowj are respectively used to denote thesets of nodes in the i-th column (i.e., Coli = {ui,j | 1 ≤ j ≤m}) and in the j-th row (i.e., Rowj = {ui,j | 1 ≤ i ≤ n}).
The dynamic grid quorum is defined as follows.
fDefinition 1 (Dynamic grid quorum): Let C f = hCW,f
be a pair of collections of node groups. C is a
dynamic grid quorum (for some f = 0, 1, . . . , min{m, n})iff• CW is the set of all possible node groups, each ofwhich (say, QfW ) satisfies the following condition.
QfW = Colk ∪{ui,j | ∀i ∃!j(f < i < k ∧1 ≤ j ≤ m)} ∪Sk
for some( k (1 ≤ k ≤ n), where{ui,k | 1 ≤ i ≤ min{k−1, f }}
1≤k≤m
Sk =
{ui,j | ∀i ∃!j(1 ≤ j ≤ i ≤ f )} otherwise

We also use the following notations. The set {ui,i | 1 ≤i ≤ min{n, m}} is called the diagonal line. Node uj,i iscalled the diagonal point of ui,j . For a given degree f , theset {ui,j | 1 ≤ i ≤ f ∧ i < j ∧ j ≤ min{n, m}} is called
the left-side exchangeable area, while the set {ui,j | 1 ≤j ≤ f ∧ i > j ∧ i ≤ min{n, m}} is called the lower
exchangeable area. Clearly, these sets are bijective by themapping of diagonal points.
Note that each of the write (read, resp.) quorums
satisfies the condition that if the quorum includes a nodein the lower (left-side, resp.) exchangeable area, then it
also includes the diagonal point. (Note, however, that theconverse does not always hold.)
To help the readers understand this definition, we
present an example of write and read quorums in a
dynamic grid quorum with degree f = 2. In this example,
nodes in the write quorum are denoted by horizontal
striped patterns. This write quorum consists of three setsof nodes: the set of all nodes in the fifth column (i.e.,
Col5 ), nodes chosen singly from the i-th column for eachi = 3, 4 (i.e., {u3,3 , u4,1 }), and the set of nodes at theintersection of the fifth row and the i-th column for eachi = 1, 2 (i.e., {u1,5 , u2,5 }). On the other hand, nodes in
the read quorum are denoted by gray shading. This readquorum consists of nodes chosen singly from each column(i.e., {u1,3 , u2,4 , u3,1 , u4,2 , u5,4 , u6,3 }), where u3,1 andu4,2 must be included because u1,3 and u2,4 are nodes in
the left-side exchangeable area.

f
CR
i

f
CR
is the set of all possible node groups, each ofwhich (say, QfR ) satisfies the following condition.
QfR = {ui,j | ∀i ∃!j(1 ≤ i ≤ n ∧ 1 ≤ j ≤ m)}such that if ui,j ∈ QfR with i ≤ f and i ≤ j ≤min {n, m} then uj,i ∈ QfR .
In this definition, the number f is called the degree of
flexibility (or the degree, for short). We may omit this if it
is clear from the context.
•

Fig. 1. Example of quorums on dynamic grid
quorum (f = 2)

3. Power Consumption Model
We introduce a power consumption model that includes
the following: strategy, load, capacity of nodes, states ofnodes, and power consumption.
Strategy. Each write (read, resp.) request is assigned to awrite (read, resp.) quorum by the probability distribution
P = hPW , PR i over hCW , CR i, satisfying the following
properties:• 0 ≤ PW (QW ) ≤ 1
for any QW ∈ CW•

0 ≤ PR (QR ) ≤ 1

for any QR ∈ CR

•X

PR (QW ) = 1

QW ∈CW•X

PR (QR ) = 1

QR ∈CRWe call this probability distribution the strategy.
Load. We define the load of a system, ld = hldWS , ldRS i,
as the number of write/read requests per unit time. Using
functions loadW and loadR , the loads of the write andread quorums (say, QW and QR ) are respectively defined
as follows.
•

loadW (QW ) = ldWS · PW (QW )(1)•loadR (QR ) = ldRS · PR (QR )(2)

Additionally, we extend these functions to represent theload of a node as follows.
X• loadW (u) =loadW (QW )(3)
QW ∈CW ,QW ∋u•loadR (u) =XloadR (QR )(4)

QR ∈CR ,QR ∋u•load (u) = loadR (u) + loadW (u)Capacity. We assume that each node u ∈ U has a capacitycap (u), which represents the upper bound of load (u)defined by the following condition.
load (u) ≤ cap (u)π (Q, ui,j ) =(Q ∪ {uj,i }) − {ui,j }(Q ∪ {ui,j }) − {uj,i }Q(ui,j ∈ Q ∧ uj,i 6∈ Q)(ui,j 6∈ Q ∧ uj,i ∈ Q)
otherwise

Note that any system obtained through this reconfiguration is also a dynamic grid quorum. Also note that thisreconfiguration is done without any data migration.
An example of this reconfiguration is presented below. Fig. 2 shows the capacity of all nodes in the
4 × 4 dynamic grid quorums C11 and C21 , where C21 isobtained by exchanging the following pairs of nodes
in C11 : hu1,2 , u2,1 i, hu1,3 , u3,1 i, and hu1,4 , u4,1 i (within
the heavy-line frames). Here we consider the case that
ldWS = 1 and ldRS = 3. In this instance, as the upper two
systems in Fig. 2 indicate, the minimum number of active
nodes in C1 and C2 are 9 and 7, respectively. On the other
hand, where ldWS = 3 and ldRS = 1, as the lower two
systems indicate, the minimum number of active nodes are
7 and 10, respectively. This shows that our reconfiguration
may remap nodes with heterogeneous capacity, thereby
reducing the power consumption of the system when theratio of write/read requests varies.

for any u ∈ UStates of nodes. We define a Boolean function On over theset of nodes, such that if load (u) 6= 0, then On (u) = 1.
Intuitively, we model the state of nodes by this function: if
On (u) = 1 then node u is active, whereas if On (u) = 0
then u is on standby and consumes no power. Note that
On (u) may be 1 even if load (u) = 0. This meansthat node u is active even though it is not executing any
operations.
Power consumption. We assume that every node in an
active state consumes the same power in the active state.
Thus we define the power consumption of a system as thenumber of active nodes.

Fig. 2. Example of dynamic grid quorum (f = 1)

In order to reduce the power consumption in an environment where the load varies, our system enables reconfiguration by exchanging a node with the corresponding
diagonal point.

Although such reconfiguration is indeed useful for reducing the power, it may violate the consistency of thereplicated data. Our reconfiguration, however, preserves
the property of consistency called one-copy serializability(cf. [2]), which guarantees that any read-operation returns
the data installed by the last committed write operation.
More precisely, the following proposition holds.

Definition 2 (Reconfiguration): The dynamic grid quorum C ′ is the reconfigured system obtained from C byexchanging node ui,j in the exchangeable areas, if C ′ ={π (Q, ui,j ) | Q ∈ C}, where the function π is defined asfollows.

′′
Proposition 1: Let C ′ = hCW, CR
i be a dynamic grid
quorum obtained from C = hCW , CR i by any number of′reconfigurations. For any QW ∈ CW , Q′W ∈ CW
, and
′
′
QR ∈ CR , the following properties hold: QW ∩ Q′R 6= φ
and QW ∩ Q′W 6= φ.

4. Reconfiguration

Proof: Due to space limitations, we only show the first
property. In this proof we use the notation u′i,j to indicate
the node at (i, j) in the grid of C ′ . From the definition of a
dynamic grid quorum, there exist i and j such that Coli ⊆QW and u′i,j ∈ Q′R . Here we consider the following cases:(1) u′i,j is in the lower exchangeable area; (2) u′i,j is in
the left-side exchangeable area; (3) otherwise.
Case (1): By the definition of reconfiguration, if u′i,j isexchanged then u′i,j = uj,i , otherwise u′i,j = ui,j . By
the definition of a dynamic grid quorum, ui,j , uj,i ∈ QW ,because QW has the corresponding diagonal node if QW
has a node in the lower exchangeable area. Thus QW ∩Q′R ∋ u′i,j .
Case (2): By the definition of reconfiguration, if u′i,j isexchanged then u′j,i = ui,j , otherwise u′i,j = ui,j . By
the definition of a dynamic grid quorum, u′i,j , u′j,i ∈ Q′R ,because Q′R has the corresponding diagonal node if Q′R
has a node in the left-side exchangeable area. On the other
hand, ui,j ∈ QW . Thus QW ∩ Q′R ∋ ui,j .
Case (3): Because u′i,j is never exchanged, ui,j = u′i,j .
Thus QW ∩ Q′R ∋ ui,j .

5. Optimization Algorithm
Our idea of power optimization is to skew the load
towards a small number of quorums. This is realized by our
optimization algorithm which shall be introduced below.
To make our discussion simpler, throughout this section we
consider the following restrictions on the states of nodes.
(C1) For any i (1 < i ≤ n) and j (1 ≤ j ≤ m),
if loadW (ui,j ) 6= 0 then On (uk,l ) = 1 for all
1 ≤ k < i and 1 ≤ l ≤ m.
(C2) For any i (1 ≤ i ≤ n) and j (1 < j ≤ m),
if loadR (ui,j ) 6= 0 then On (ui,l ) = 1 for all
1 ≤ l < j.
Under these restrictions, we consider the following
problem.
Problem 1: For a given dynamic grid quorum C, acapacity cap, and a system load ld of C, find a strategy P
that minimizes the power consumption of C.
In order to solve this problem, generally, the number ofquorums increases exponentially with the number of nodes.
This results in an explosion of the search space for the
optimization. On the other hand, the power consumptionof the system is determined only by the total load of eachnode. From this observation, the key idea in optimizing thestrategy is to first divide each quorum into its components
and to consider only the loads thereof. Then we limit the
search space to a subset created from a special type ofload, denoted by load′ , from which we obtain our aimed
optimal strategy.

In terms of load′ , we find an optimal solution to
Problem 1 by the following procedure: we first find an
optimal load′ then construct an optimal strategy from thisoptimal load′ . Here, P opt is used to denote a strategy
obtained by this procedure. Then the following theorem
holds.
Theorem 1: P opt is an optimal solution to Problem 1.
The outline of the proof of Theorem 1 is as follows.
First, we define load′ . Next, we prove Lemmas 1 and
2, which verify that an optimal strategy can be obtained
from an optimal load′ . Finally, we prove Lemma 3, which
confirms that we can find an optimal load′ using ouralgorithm.
Definition 3 (Special type of load): For a given system
C f and its load ld, we define load′ consisting of thefollowing four functions.
′+• loadWN : {ui,j | 1 ≤ i < n ∧ 1 ≤ j ≤ m} → R′+• loadWC : {Coli | 1 ≤ i ≤ n} → R′+• loadRN : {ui,j | 1 ≤ i ≤ n ∧ 1 ≤ j ≤ i} → R′+• loadRT : T → R
where T is the set of ~t = ht1 , . . . , tf i defined as follows.
• ti ∈ {0, i+1, i+2, . . . , m}
• If ti = j then tj = 0 for any i.
• If ti = k and k 6= 0 then tj 6= k for any i 6= j.
Here load′ satisfies conditions (5) to (10) given below.
n
m
X
X
′
loadWN (ui,j ) =load′WC (Colk )
•
j=1

k=i+1

for any i (f < i < n) (5)•iXload′WN (ui,j ) =

j=1

•

n
X

load′WC (Colk )k=m+1

for any i (1 ≤ i ≤ f ) (6)load′WN (ui,j ) = load′WC (Colj )for any ui,j in the left-side exchangeable area (7)•nXload′WC (Colk ) = ldWS

(8)

k=1
•

X

~
t∈T,ti =j
load′RT ~t ≤ load′RN (uj,i )for any ui,j in the left-side exchangeable area (9)

•

i
X
j=1

load′RN (ui,j ) +

m
X

X


load′RT ~t = ldRS

j=i+1 ~t∈T,ti =j

for any i (1 ≤ i ≤ f ) (10)The intuitive meaning of load′ is as follows. A write
quorum can be divided into a single column and theother part. load′WC (Col) represents the total write loadof column Col, while load′WN (u) represents the total
write load of node u in the other part. On the other hand,load′RT ~t represents the total read load of that part of theread quorum, included in the left-side exchangeable area.
Here ~t represents this part. More precisely, ti ∈ ~t denotesthat the part includes node ui,j with j = ti . load′RN (u)represents the total read load, where u is not in the left-side
exchangeable area.
Using the notion of load′ , instead of loadW and loadR(introduced by Eqs. 3 and 4), we can also define load′W
and load′R , the total write and read loads, respectively, ofeach node, as given below.
• load′W (ui,j ) = load′WN (ui,j ) + load′WC (Coli )(11)• load′R (ui,j ) =

P
 ~

′
t∈T,ti =j loadRT

load′ (u )
i,j
RN


~t ui,j is in the left-side
exchangeable area

(12)

otherwise

Moreover, in terms of this definition, we can naturally
define the power consumption, similarly to loadW and
loadR . Then, we obtain the following lemma.
Lemma 1: For any system C f , any system load ld of
C , and any load′ , we can obtain a strategy P whose power
consumption is the same as load′ .
fProof: It is sufficient to show that loadW (u) =load′W (u) and loadR (u) = load′R (u) for any u. We
define PW and PR as (13) and (14), respectively.
load′WC (Colk )• PW (QW ) =ldWS
Yload′ (u )Pm WN′ i,j·
l=1 loadWN (ui,l )ui,j ∈QW ,f <i<kY·
g1 (ui,j , k)•

PR (QR ) = load′RT ~t ·Yui,j ∈QR•

WN

g2 (ui,j ) = load′RN (ui,j ) −

i,l

X

~
t∈T,tj =iload′RT (~t )Also, the following lemma, which is the converse ofLemma 1, is provable.
Lemma 2: For any system C f , any system load ld of
C f , and any strategy P , we can obtain a load′ whose power
consumption is the same as P .
Proof: We define load′WN , load′WC , load′RN , andas (15), (16), (17), and (18), respectively.
X′
loadW (QW ) (15)• loadWN (ui,j ) =load′RT

QW ∈CW ,QW ∋ui,j ,QW 6⊇Coli•load′WC (Colk ) =X

loadW (QW )X

loadR (QR )(16)

QW ∈CW ,QW ⊇Colkload′RN (ui,j ) =for any ui,j ∈ U such thatui,j is not in the left-side exchangeable area (17)
•

(13)

(14)

Here g1 , g2 , and g3 are functions defined as follows.
(1k≤m• g1 (ui,j , k) =load′WN (ui,j )Piotherwiseload′ (u )l=1where Case 1 covers i ≤ f , uj,i 6∈ QR , and ui,j in thelower exchangeable area; Case 2 deals with i > f and,if uj,i ∈ QR then j > f ; and Case 3 covers all otherpossibilities.
Then by the definitions of hloadW , loadR i (i.e., (1)-(4)),
load′ (i.e., (5)-(10)), and hload′W , load′R i (i.e., (11)-(12)),
we can derive our required equations.

QR ∈CR ,QR ∋ui,jg2 (ui,j )g3 (QR , ui,j )where ~t satisfies ti=j6=0 iff ui,j ∈QR and i<jg3 (QR , ui,j ) =

f
i

X
X

X
′


load
(u
)
−
load′RT ~t (Case1)
i,l

RN



k=1 ~
l=1
t∈T,tk =i



f
X
X

(Case2)
ldRS −
load′RT ~t



k=1 ~

t
∈T,t
=i
k

X



load′RN (ui,j ) −load′RT (~t )(Case3)~t∈T,tj =i•ui,j ∈QW ,i≤fwhere k is a number such that Colk ⊆ QW•

load′RT ~t =X

loadR (QR )(18)

QR ∈T (~t)

Here T ~t in (18) is a class of read quorums such thatfor any QR ∈ T ~t , if ti = j and j 6= 0, then ui,j ∈ QR
for any i and j, and ui,j is in the left-side exchangeable
area.
From Eqs. (15) to (18) and Eqs. (1) to (4) we can derive(5) to (10). This guarantees that load′ defined by (15) to(18) satisfies conditions (5) to (10). Moreover, in addition
to the above derivation, by (11) and (12) we can obtainour required equations.


The algorithm (called OL) to obtain an optimal load′ , ispresented in Fig. 3. The algorithm can be divided into threesteps. Step 1, comprising lines 1 to 7 in Fig. 3, minimizes
the number of active nodes for write requests (called thewrite-area) so as to satisfy (5) to (10). At the end of Step
1, a minimum V for the write-area has been obtained.
Step 2, comprising lines 8 to 14, minimizes the numberof active nodes for read requests (called the read-area)
so as to satisfy (5) to (7). At the end of Step 2, V is
the union of the minimum write-area and minimum readarea. Because Step 2 disregards (10), some active nodes
might be added to satisfy (10). We call this set of nodes
the additional-area. Step 3, comprising the rest of thisalgorithm, minimizes the additional-area and then returns
an optimal solution.
Next we explain the details of sub-algorithms LP1 andLP2 used in Steps 1 and 3, respectively. LP1 consists oflinear programming, which returns true if and only if there
exists a basic feasible solution of load′ to the constraints
represented by the following conditions.
(5) to (10).
The condition of capacity.
′• loadWC (Coli ) = 0 for all i(K < i ≤ n) .
••In Step 1, if there is no feasible area even with K = n,then there exists no solution. In this case, the algorithm
terminates without finding a solution.
LP2 also consists of linear programming, which returns
one of the basic feasible solutions of load′ , if it exists,
to the constraints represented by the following conditions;otherwise it returns nil.
(5) to (10).
The condition of capacity.
′′• loadW (ui,j )+loadR (ui,j ) = 0 for ui,j 6∈ V and k < i.
••

Now we show that the load′ obtained by this algorithm
is optimal.
Lemma 3: For any dynamic grid quorum C f , any system load ld of C f , and any capacity cap, Algorithm OL
returns an optimal solution load′ , which minimizes thepower consumption.
Proof sketch: Let S be the set of active nodes
determined by the solution obtained by this algorithm.
Here we consider SW , SR , and SA , which are the write-,read-, and additional-areas of S, respectively. Thus, toprove this lemma it is sufficient to show that each of SW ,SR , and SA is minimum.
Clearly, for SW and SR , these are the minimum sets tohandle the given load ldWS and ldRS , respectively. That is
because if this were not the case, Step 1 or the inner loopof Step 2 controlled by I would terminate prematurely.
s,tTo find SA , Step 3 repeatedly generates a set (say, CA)of candidates, by the following operations OP1 and OP2
so as to enumerate all possible candidates.
s,t+1
s,t
(OP1) Generate CAfrom CAby adding ui,j to eachs,t′candidate SA ∈ CA , where ui,j satisfies i ≤ f ,′′ui,j 6∈ SA∪ SR , and ui,l ∈ SA
∪ SR for all l < j.

input:U, n, m, cap, ld
01: {Step 1 starts here.}
02: K ← 0 ;03: while LP1 returns false
04: if K = n then05:
exit “NO SOLUTION” ;06: K ←
SK +1 ;
07: V ← K
l=1 Coll ;08: {Step 2 starts here.}
09: if ldRS 6= 0 then
10: for I = 1 to n
11:
for J = 1 to ˘m¯
12:VP← V ∪ uI,J ;13:
if u∈V,u∈ColI cap (u) ≥ ldRS then14:
break ;
15: {Step 3 starts here.}
16: V ← {V }, V ′′ ← U , P ← nil, L ← K ;17: loop
18: for all V ′ ∈ V
19:
if LP2 returns some load′ then20:
if |V ′ | < |V ′′ | then21:
V ′′ ← V ′ , PP
← load′ obtained by LP2 ;22:
if |V ′′ − V | ≤ L+1
i=k (m − |V ∩ Coli |) then23:
return P ;
24:
else
25:
V ← {V ∪ ColL+1 }, L ← L + 1 ;26:
next loop ;27: W ← φ ;28: for all V ′ ∈ V
29:for I = L + 1
˘ to n¯
30:
T ← max j | uI,j ∈ V ′ ;31:
if T < f ˘then ˘¯¯32:
W ← V ′ ∪ uI,T
∪W ;33: V ← W ;34: if V = φ then35:
V ← {V ∪ ColL+1 }, L ← L + 1 ;Fig. 3. Algorithm OL
s+1,0
s,0
′
(OP2) Generate CAfrom CAby adding Cols+1⊆s,0′Cols+1 to each candidate SA ∈ CA such that′u ∈ Cols+1
if and only if u 6∈ SR .
0 ~1
h
~
~
Let CA , CA , . . . , CA be the sequence of sets of candidatessgenerated in Step3, where for each 0 ≤ s ≤ h, C~A
=
s,0
s,1
s,hs
for some hs . Here, for any s and
CA , CA , . . . , CAs,tt, each candidate in CA
satisfies (C1) and (C2). In thiss,tsequence, there exists CA∋ SA for some s and t, where
SA is the minimum among all the candidates for each ofwhich LP2 returns a solution.
Here,
there is no smallers′ ,t′
s′′ ,t′′candidate than SA in CA
nor CAfor any s′ , s′′ , t′ , andt′′ such that s′ > h and s′′ ≤ h and t′′ > hs′′ . Therefore,
SA is a minimum additional-area.

Proof of Theorem 1: Let load′ be the solution
obtained by Algorithm OL. Then, by Lemma 3, load′ is an
optimal solution in the set of special type of loads. Thus,by Lemma 1, we can obtain a strategy P opt whose power
consumption is the same as load′ . Moreover, P opt is an
optimal strategy, because if there exists another strategy(say, P ′ ) whose power consumption is smaller than thatof P opt , then by Lemma 2, a better solution also exists inthe set of special type of loads. This contradicts Lemma
3.
Remark: restrictions on the state of nodes. If wedisregard either of the restrictions (C1) or (C2), there may
be a better solution than that obtained by our algorithm.
For example, let SR be the read-area, k the number ofcolumns in the write-area, and load′ a special type of load
obtained by the algorithm.
P If there is some set of nodes′
SR⊆ SR that satisfies u∈(S ′ ∩Coli ) cap (u) ≥ ldRS forRP
any Coli , and ~t∈T,ti =j load′RT ~t = 0 for any ui,j suchthat 1 ≤ i ≤ k < j ≤ min {n, m} and uj,i 6∈ VR , then the′nodes SR − SR
can be reduced if we disregard assumption(C2).
Remark: computational complexity. By using the notionof load′ , the computational complexity of our proposed
algorithm is decreased. Indeed, as far as our experiments
are concerned, we can find optimal solutions in feasible
time for all cases of the simulations in the next section.
However, the following two factors may still cause a search
space explosion: the number of loops in Step 3 (eventhough this step is not used in many cases) and the numberof constraints for load′RT , where the computational complexities are O(f n ) and O(mf ), respectively. A possible
way to avoid such exponential growth is to restrict thedegree f to a small number, but an improvement to ouralgorithm is still needed. This shall be investigated as oneof our future works.

6. Simulation Results
In the evaluation of this section, we consider the following three systems for a 10 × 10 grid: dynamic grid quorum
with reconfiguration (DG), and fixed allocation of nodes
optimized for write requests (WG) and read requests (RG),
respectively. First we evaluate the impact of the write/readratio for each case where the system load is low, medium
or high. In contrast to the above settings, we also evaluate
the impact of system load, where the write/read ratio isfixed but the total number of requests varies.
Parameters and Settings. Each system in the evaluationconsists of 70 nodes with capacity c and 30 nodes withcapacity 2c. In the WG and RG, the nodes with 2c areallocated in Coli and Rowi (1 ≤ i ≤ 3), respectively.
The DG is a dynamic grid quorum with degree f = 3,
whose node allocation is the same as in the WG. For the
impact analysis of the write/read ratio, we use 2.5c, 5c,
and 7.5c as the values for low, medium, and high loads inthe system, respectively. This setting arises from the factthat the write and read capacity for a grid of the same
size, comprising homogeneous nodes with capacity c is
10c and 6.5c, respectively. For the impact analysis of thesystem load, we consider the write/read requests to be 1/3,

which is also used as the default parameter in [14].
Impact of write/read ratio in the case of low load. Fig.
4 shows that the power consumption of the DG is less thanthat of both the WG and RG for all ratios. Additionally,
compared with the WG and RG, our system saves on
average 12% and 13%, respectively, and up to 27% and
32% of power, respectively, for all ratios. The results of thissimulation show that our system effectively reduces power
consumption when compared with both the WG and RG.
Impact of write/read ratio in the case of medium load.
Fig. 5 shows that the power consumption of the DG is theleast for the range 0% to 70% of the write ratio. Above
70% of the write ratio, our system consumes more power
than the WG. The DG, however, does not exceed the power
consumption of the RG for all ratios. Considering moredetailed results, the DG consumes on average 0.2% more
power than the WG and 10% less than the RG for all ratios.
Moreover, compared with the WG and RG, our systemsaves up to 28% and 24% of power, respectively, although
it consumes twice as much as the WG in the worst case.
The results of this simulation show that our system is lesseffective for all write ratios with medium load than withlow load. However, our system is still efficient for a wide
range of write ratios.
Impact of write/read ratio in the case of high load.
Where ldWS + ldRS = 7.5c, the DG cannot handle a write
ratio above 70%, whereas the WG and RG can. However,compared with the WG and RG, our system saves on
average 1% and 6%, respectively, for a write ratio in therange 0% to 70%. The results of this simulation show that
our system may not be able to handle a high write ratiowith high load. However, our system is still able to savesome power for other write ratios.
Impact of load growth. Fig. 6 shows that the power
consumption of the DG is the least of all the systems forall system loads. Compared with the WG and RG, oursystem saves on average 12% and 6%, and up to 27% and
22% of power, respectively, for all ratios. The results ofthis simulation show that our system is effective for any
system load.

7. Conclusions and Future WorkIn this paper, we presented a power-aware quorum
system called the dynamic grid quorum. To reduce power
consumption, we introduced an optimization algorithm for
skewing the workload towards a small number of quorums.
Moreover, we proposed a reconfiguration technique thatallows the exchanging of nodes without data migration. We
also evaluated our technique by comparing the proposedsystem with static quorums. The results showed that oursystem saved on average between 6 and 12% with a 1/3
write operation ratio.

Fig. 4. Number of active nodes(ldWS +ldRS = 2.5c)

Fig. 5. Number of active nodes (ldWS +ldRS = 5c)

There are several possible directions in which this work
can be developed. As mentioned in Section 5, we areinterested in an improvement to our algorithm to avoid thecase that results in a search space explosion. We are alsointerested in some extensions of our technique, especiallyby modeling heterogeneity of power consumption and timerequired for the state transition of nodes, that were notconsidered in this paper.

Acknowledgments
This study was supported in part by the Global COE
Program on “Cybernics: fusion of human, machine, andinformation systems.”

References[1] D. Agrawal and A.-E. Abbadi. An efficient and fault-tolerant solution
for distributed mutual exclusion. ACM Trans. on Computer Systems,
9(1):1–20, 1991.
[2] P.-A. Bernstein, V. Hadzilacos, and N. Goodman. Concurrency
Control and Recovery in Database Systems. Addison Wesley, 1987.
[3] S. Cheung, M. Ammar, and M. Ahamad. The grid protocol: A highperformance scheme for maintaining replicated data. IEEE Trans.
on Knowledge and Data Engineering, 4(6):582–592, 1992.

Fig. 6. Number of active nodes (ldWS : ldRS = 1 : 3)

[4] D. Colarelli and D. Grunwald. Massive arrays of idle disks forstorage archives. Proc. of the ACM/IEEE Conf. on Supercomputing,pages 1–11, 2002.
[5] I. Frain, R. Basmadjian, J.-P. Bahsoun, and A. M’zoughi. How
to improve the scalability of read/write operations with dynamic
reconfiguration of a tree-structured coterie. Proc. of the Int’l. Conf.
on Parallel Processing Workshops, pages 123–134, 2006.
[6] A. Fu. Delay-optimal quorum consensus for distributed systems.
IEEE Trans. on Parallel and Distributed Systems, 8(1):59–69, 1997.
[7] D. Gifford. Weighted voting for replicated data. Proc. of the ACM
Symposium on Operating Systems Principles, pages 150–162, 1979.
[8] T. Ibaraki and T. Kameda. A theory of coteries: Mutual exclusion
in distributed systems. IEEE Trans. on Parallel and Distributed
Systems, 4(7):779–794, 1993.
[9] D. Li and J. Wang. EERAID: energy efficient redundant and inexpensive disk array. Proc. of the ACM SIGOPS European Workshop,
6 pages, 2004.
[10] X. Lin. Delay optimization in quorum consensus. Algorithmica,
38(2):397–413, 2004.√[11] M. Maekawa. A n algorithm for mutual exclusion in decentralized systems. ACM Trans. on Computer Systems, 3(2):145–159,
1985.
[12] D. Peleg and A. Wool. Crumbling walls: A class of practicaland efficient quorum systems. Distributed Computing, 10(2):87–97,
1997.
[13] E. Pinheiro and R. Bianchini. Energy conservation techniques fordisk array-based servers. Proc. of the Int’l. Conf. on Supercomputing,pages 68–78, 2004.
[14] E. Pinheiro, R. Bianchini, and C. Dubnicki. Exploiting redundancy
to conserve energy in storage systems. Proc. of the joint Int’l Conf.
on Measurement and Modeling of Computer Systems, pages 15–26,
2006.
[15] T. Tsuchiya, M. Yamaguchi, and T. Kikuno. Minimizing the
maximum delay for reaching consensus in quorum-basedmutual
exclusion schemes. IEEE Trans. on Parallel and Distributed Systems,
10(4):337–345, 1999.
[16] J. Wang, H. Zhu, and D. Li. eRAID: Conserving energy inconventional disk-based raid system. IEEE Trans. on Computers,
57(3):359–374, 2008.
[17] C. Weddle, M. Oldham, J. Qian, A.-I. Wang, P. Reiher, andG. Kuenning. PARAID: A gear-shifting power-aware RAID. Proc. of
the USENIX Conf. on File and Storage Technologies, pages 245–260,
2007.
[18] X. Yao and J. Wang. RIMAC: a novel redundancy-based hierarchical cache architecture for energy efficient, high performance storage
systems. Proc. of the ACM SIGOPS/EuroSys European Conf. on
Computer Systems, pages 249–262, 2006.
[19] Q. Zhu, Z. Chen, L. Tan, Y. Zhou, K. Keeton, and J. Wilkes.
Hibernator: helping disk arrays sleep through the winter. ACM
SIGOPS Operating Systems Review, 39(5):177–190, 2005.