Noname manuscript No.
(will be inserted by the editor)

Dynamic Grid Quorum: A Reconfigurable Grid Quorum
and Its Power Optimization Algorithm
Munetoshi Ishikawa · Koji Hasebe · Akiyoshi Sugiki · Kazuhiko Kato

Received: date / Accepted: date

Abstract In this paper, we present the dynamic grid
quorum, a method for reducing the power consumption of large-scale distributed storage systems. The basic principle of our approach is to skew the workload
towards a small number of quorums. This can be realized by the following three techniques. First, our systemallows reconﬁguration by exchanging nodes without any
data migration, so that high-capacity nodes can be reallocated to busier quorums. Second, for more eﬀective
skewing of the workload, we introduce the notion ofdual allocation, which makes it possible to consider two
distinguished allocations in the same grid for write andread quorums. Finally, we present an optimization algorithm to ﬁnd a pair of strategy and an allocation ofnodes, which minimizes power for a given system setting and its workload. We also demonstrate that the dynamic grid quorum saves, on average, 14%–25% energy
compared with static conﬁgurations, when the intensityof the total workload was changed.
Keywords distributed storage, quorum system,
grid quorum, power saving, optimization algorithm,
reconﬁguration
Correspondence to:M. Ishikawa · K. Hasebe · A. Sugiki · K. Kato
Graduate School of Systems and Information Engineering, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Ibaraki 305–8573,
Japan
E-mail: munetoshi@osss.cs.tsukuba.ac.jp
K. Hasebe
E-mail: hasebe@iit.tsukuba.ac.jp
A. Sugiki
E-mail: sugiki@cs.tsukuba.ac.jp
K. KatoE-mail: kato@cs.tsukuba.ac.jp

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 business computing systems, reliable, available, and costeﬀective 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 writeall technique, the quorum approach allows ﬂexibility
in storage conﬁguration and decentralized management
for consistency control. Since the ﬁrst quorum paper [7]was presented, much research has focused on investigating the possibilities of quorum systems. These studies
are wide-ranging, from desired conﬁgurations in quorum systems [13, 1, 3, 14] to performance optimization
methods that minimize the communication delays [6,17,12]. On the other hand, little attention has been
paid to reducing power consumption in quorum systems, which is necessary in terms of green computing,which has recently become of prime interest to practitioners.
In this paper, we present the dynamic grid quorum,a technique for reducing storage power consumption.
As its name implies, our approach is based on a grid
quorum [3], but the basic principle of our approach isto skew the workload towards a small number of quorums. This can be realized using the following three concepts, which are extensions of our previous work [10].
First, the dynamic grid quorum provides reconﬁguration by exchanging nodes without any data migration.
Although the node exchange idea comes from a study
on tree-based quorums [5], much of the work has had tobe adapted for grid quorums. Since we also consider heterogeneity in nodes, this reconﬁguration method allows

2high-capacity nodes to be allocated to busier quorums
to reduce the number of active nodes. Even when exchanging nodes in a grid quorum, our reconﬁguration
method preserves the consistency of replicated data,
namely the one-copy serializability (cf. [2]). Second, formore eﬀective skewing of the workload, we introduce
the notion of dual allocation. In the original grid quorum system [3], the nodes are allocated in a rectangular grid then grouped into write and read quorums in a
speciﬁc way according to this allocation. The dual allocation is an extension of this grouping method. Thatis, to group the nodes into quorums, we consider two
distinguished allocations in the same grid for write andread quorums. In addition, the one-copy serializability
still holds for this extension. Finally, we present an optimization algorithm to ﬁnd a pair of a strategy (i.e.,
probability distribution over the quorums, determining
which quorum is selected for each write/read request)
and an allocation, which minimizes power for a given
system setting and its workload. Despite the exponential growth of the possible combinations of quorums andallocations with respect to the number of nodes, our algorithm reduces the computational complexity to ﬁnd
a solution using several techniques.
To evaluate the eﬀectiveness of the proposed dynamic grid quorum with dual allocation, we compared
our approach under three alternative conﬁgurations:
static write-optimized, static read-optimized, and dynamic reconﬁguration with no dual allocation (i.e., single allocation). From the simulations, we observed thatour dynamic grid quorum with dual allocation saved, on
average, 14.1–25.2% energy compared with the static
conﬁgurations, when the intensity of the total workload was changed. In addition, compared with the caseof single allocation, our proposed system saved, on average, 10.4% energy, which indicated that our dual allocation skews workload more eﬀectively.
This paper is organized as follows. Section 2 presents
related work. Sections 3 and 4 introduce the dynamic
grid quorum and its power consumption model. Section 5 gives the deﬁnition of our reconﬁguration. Section 6 introduces the notion of dual allocation and its
reconﬁguration. Section 7 introduces the algorithm andproves that it minimizes the power consumption of the
dynamic grid quorum. Section 8 presents the simulation results. Finally, Section 9 concludes the paper anddiscusses future research.

2 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 workload, which is also used inthis paper. In MAID [4] and PDC [15], popular data
are concentrated on speciﬁc disks. In DIV [16], original and redundant data are separated onto diﬀerent
disks, thereby allowing write/read requests to be concentrated on the disks with original data. In RIMAC[20], eRAID [18], and EERAID [11], a data access on
a disk in standby mode is transformed into accesses on
active disks or caches, and then the required data arereconstructed from the parities obtained during theseaccesses. In Hibernator [21] and PARAID [19], data arecollected or spread to adapt to changes in operationalloads.
Although these studies in the literature restrict theirscope to storage with a speciﬁc kind of central controller to manage the data access, recent work such as
Harnik et al., [8] addresses power-saving in large-scale
distributed storage system, whose prime application iscloud computing. Our target application is similar tothis study, but our main motivation is to achieve reliable, available, and cost-eﬀective distributed data management by taking the quorum approach, which has notbeen thoroughly investigated.
3 Dynamic Grid Quorum
Our proposed system is based on the grid quorum [3],which is a special kind of write-read coterie [9], in which
the nodes are allocated in a rectangular grid. A writeread coterie C is a pair hCW , CR i of collections of nodegroups, called quorums, where CW and CR represent
write quorums and read quorums. For readability, we
use the notation CA to denote CW or CR . (Similar notations are also used for other notions.) Throughout thispaper, we ﬁx the numbers of columns and rows of thegrid as n and m. Each intersection point (often justcalled point) of the i-th column (from the left) and thej-th row (from the bottom) is denoted by (i, j). The
set of all points in the grid is denoted by D. We also
ﬁx the underlying set of nodes as U = {u1 , . . . , un·m }whose elements are allocated to the points in the gridby bijective mapping. We refer to this allocation by themapping v : D → U . We thus deﬁne the node at point(i, j) by v(i, j). In addition, the set {(i, i) | 1 ≤ i ≤min{n, m}} is called the diagonal line. The point (j, i)
is called the diagonal point of (i, j).
To formally deﬁne the dynamic grid quorum, we
introduce the notion of degree as follows. Degree, denoted by f , is a pair hc, ri of natural numbers with0 ≤ c < min{n, m} and 2 ≤ r ≤ min{n, m}, respectively. For given degree f , the set of exchangeable pairs(denoted by E f ) is deﬁned by {h(i, j), (j, i)i | i ≤ c∧r ≤3j ∧ i < j}. In addition, for given E f , the sets of the ﬁrst
and the second projections of all the elements of E f(i.e., {p | hp, p0 i ∈ E f } and {p0 | hp, p0 i ∈ E f }, resp.) arefcalled left-side exchangeable points (denoted by Eleft)

Qv,fR = {v(i, j) | ∀i∃!j(1 ≤ i ≤ n ∧ 1 ≤ j ≤ m)}fsuch that if v(i, j) ∈ Qv,fR and (i, j) ∈ Eleft thenfand lower exchangeable points (denoted by Elow). Thesymbol f may be omitted if it is clear from the context.
We present an example of the exchangeable points
below.

Throughout this paper, we may omit v as well as f
if these are clear from the context.
To help the reader understand this deﬁnition, we
present an example of write and read quorums below.

Example 1 Fig. 1 depicts the exchangeable points of
6 × 6 grid with f = hc, ri = h4, 3i. In this ﬁgure, theleft side and the lower exchangeable areas of this caseare indicated as the area within the heavy-lines and thearea within the dashed-lines.

Example 2 Fig. 2 depicts a write quorum and a readquorum in the 6 × 6 dynamic grid quorum with f =h2, 4i. In this ﬁgure, the points of nodes in the write
quorum are denoted by vertical striped patterns. This
write quorum consists of the following two sets: the setof all nodes on the ﬁfth column (i.e., v(Col(5))), nodes
chosen singly from the i-th column for each i = 1, . . . , 4(i.e., {v(1, 5), v(2, 5), v(3, 1), v(4, 4)}) where v(1, 5) andv(2, 5) must be chosen because (5, 1), (5, 2) ∈ Elow . On
the other hand, nodes in the read quorum are denotedby gray shading. The read quorum consists of nodes
chosen singly from each column (i.e., {v(1, 4), v(2, 1),v(3, 6), v(4, 1), v(5, 5), v(6, 2)}) where v(4, 1) must be included because (1, 4) ∈ Eleft .

v(j, i) ∈ Qv,f
R .

u
t

Fig. 1 Exchangeable points with f = hc, ri = h4, 3i

Finally, for readability we use the following notations. Col(i) and Row(j) are respectively used to denote the sets of points on the i-th column (i.e., Col(i) ={(i, j) | 1 ≤ j ≤ m}) and on the j-th row (i.e., Row(j) ={(i, j) | 1 ≤ i ≤ n}). Notations v(Col(i)) and v(Row(j))
are used to denote the sets of nodes on Col(i) andRow(j) determined∪jby allocation v. Also, [i, j] is used
to denote the set k=i Col(k).

Fig. 2 Write and read quorums with f = hc, ri = h2, 4i

In terms of the notions previously introduced, thedynamic grid quorum is deﬁned as follows.

4 Power Consumption Model

Definition 1 (Dynamic grid quorum) Let C v,f =
v,f
v,f
hCW
, CR
i be a pair of collections of node groups. C v,fis a dynamic grid quorum if

We introduce a power consumption model that includes
the following: strategy, load, capacity of nodes, statefunction, and power consumption.

v,fis the set of all possible node groups, each of– CW
which (say, Qv,f
W ) satisﬁes the following condition:

Qv,f
W = {v(i, j) | (i, j) ∈ Col(k) ∨ ∀i∃!j(1 ≤ i <k ∧ 1 ≤ j ≤ m)} for some k (1 ≤ k ≤ n) such that––fif (i, j) ∈ Col(k) ∩ Elow
then v(j, i) ∈ Qv,fW ;fif v(i, j) ∈ Qv,f
and
(i,
j)
∩
E
then
v(j, i) ∈
W
left
v,f
QW .

v,f
is the set of all possible node groups, each of– CR
which (say, Qv,f
R ) satisﬁes the following condition:

Strategy. Each write/read request is assigned to awrite/read quorum by the probability distribution P =hPW , PR i over hCW , CR i satisfying the following properties:– 0 ≤ PA(QA ) ≤ 1∑–
PA(QA ) = 1.

for any QA ∈ CA .

QA ∈CA

We call this probability distribution the strategy.
Load. We deﬁne the load of a system, ld = hldW , ldR i,
as the number of write/read requests per unit time. We

4also deﬁne functions loadW and loadR which represent
the loads of the write/read quorums (say, QW and QR )as follows.
loadA(QA ) = ldA · PA(QA ).

(1)

In addition, we extend these functions to represent
the load of a node (say, u) as follows.
– loadA(u) =∑loadA(QA ).

(2)

QA ∈CA ,QA 3u– load(u) = loadW (u) + loadR(u).

(3)

Capacity. We assume that each node u ∈ U has acapacity cap(u), which represents the upper bound ofload(u) deﬁned by the following condition.
load(u) ≤ cap(u).

(4)

We also introduce the notion of overload as follows.
Node u is overloaded if load(u) > cap(u). A system
is overloaded if there is at least one overloaded node.
A system is overloaded with the nodes up to the k-th
column if the system is overloaded for any strategy suchthat the load of every node from the right of the k+1-th
column is 0 (i.e., loadW (v(i, j)) = 0 for any i > k andfor any j).
State-function. We introduce the state-function On, a
Boolean function over the set of nodes, which satisﬁes
the following condition.
If load(u) 6= 0 then On(u) = 1.

(5)

We model the state of the nodes by this function. Thatis, if On(u) = 1 then node u is active, whereas if On(u) =0 then u is on standby and consumes no power. Notethat 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 inan active state consumes the same power. Thus we deﬁne the power consumption of a system by the number∑of active nodes (i.e., u∈U On(u)) denoted by |On|.

5 Reconfiguration
To reduce the power consumption in an environment
where the load varies, our system enables reconﬁguration by exchanging a node with the corresponding
diagonal point. This can be deﬁned as the change ofallocation mapping.

Definition 2 (Reconfiguration)

For any (i, j) ∈(i,j)

Eleft , let −−−→ be a binary relation over the allocations(i1 ,j1 )such that if v −−−−→ v 0 then for any i2 and j2
v(i2 , j2 ) ={v 0(j2 , i2 ) if (i1 = i2 ∧ j1 = j2 ) ∨ (i1 = j2 ∧ j1 = i2 )v 0(i2 , j2 ) otherwise.
utE0

In addition, for any E 0 ⊆ Eleft , the notation v −→ v 0
is used to represent that v 0 is obtained from v by successive exchanges of all the points in E 0 with their diagonals. In this case, v 0 is called the reconfigured allocationfrom v. Here we note that, obviously, for any v and v 0 ,E0

E0

if v −→ v 0 then v 0 −→ v. In addition, v 0 can be obtained from v regardless of the order of exchanges. For
the sake of convenience, as a special case, we introduceφthe expression v −→ v 0 to represent that v 0 can be obtained from v without any operation, i.e. v = v 0 . Notethat any system obtained through reconﬁgurations is
also a dynamic grid quorum.
We present an example of this reconﬁguration below.
Example 3 Fig. 3 shows the capacity of all nodes in0
the 4 × 4 dynamic grid quorums C v and C v , wherev 0 is obtained from v by reconﬁguration with E 0 ={(1, 2), (1, 3), (1, 4)}. (Thus, v is also obtained from v 0
by reconﬁguration with the same set, E 0 .) Here we consider the case that ldW = 1 and ldR = 3. In this instance, as the upper two systems in this ﬁgure indicate, the minimum number of active nodes in system0
C v and its reconﬁgured system C v are 9 and 7. On
the other hand, where ldW = 3 and ldR = 1, as thelower two systems indicate, the minimum numbers of0
active nodes in system C v and its reconﬁgured systemv
C are 10 and 7. This shows that our reconﬁguration
may remap nodes with heterogeneous capacity, thereby
reducing the power consumption of the system when
the ratio of write/read requests varies.
Although such reconﬁgurations are indeed useful for
reducing the power, it may violate the consistency of
the replicated data. Our reconﬁguration, 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. This can be guaranteed by thefollowing proposition.
Proposition 1
E0

Let v and v 0 be allocations which sat0

isfy v −→ v 0 for some E 0 ⊆ Eleft . C v and C v are dynamic grid quorums consisting of the same nodes. For56 Dual Allocation
As deﬁned in Section 3, in the dynamic grid quorum,
the nodes are allocated to the points in an underlying
grid, and the nodes are grouped into write and readquorums in a speciﬁc way according to this allocation.
Then, as explained in Section 5, by changing the allocation we can gather high-capacity nodes to a busierarea while preserving the one-copy serializability, that
may reduce the number of nodes in the active mode.
Here we note that this allocation is just a logical mapping, so our reconﬁguration does not change the physical position of any node. From this consideration, we
can separate allocations for write and read quorums,
and then the reconﬁgurations for write and read quorums independently. This is called the dual allocation,
which reduces power in a more eﬀective way than withthe single allocation.
We explain the idea behind this dual allocation byusing a simple example below. (See also Fig. 4 for thegraphical presentation.)
E0

Fig. 3 Reconﬁgurations −−→ with E 0 = {(1, 2), (1, 3), (1, 4)}
0

0

v
v
v
any QW ∈ CW
, Q0W ∈ CW
, and Q0R ∈ CR
, the following
two properties hold: QW ∩ Q0R 6= φ and QW ∩ Q0W 6= φ.

Proof Due to space limitations, we show only the ﬁrst
property. From the deﬁnition of a dynamic grid quorum,0
for any QW ∈ CW and Q0R ∈ CR
, there exist i and jsuch that v(Col(i)) ⊆ QW and v 0(i, j) ∈ Q0R . Here we
consider the following three cases: (a) (i, j) ∈ Elow ; (b)(j, i) ∈ Eleft ; (c) otherwise.
Case (a): By the deﬁnition of reconﬁguration, if(i, j) ∈ E 0 then v 0(i, j) = v(j, i), otherwise v 0(i, j) =v(i, j). By the deﬁnition of a dynamic grid quorum,v(i, j), v(j, i) ∈ QW , because QW has the corresponding
diagonal node if QW has a node in the lower exchangeable area. Thus QW ∩ Q0R 3 v 0(i, j).
Case (b): By the deﬁnition of reconﬁguration, if(i, j) ∈ E 0 is exchanged then v(i, j) = v 0(j, i), otherwise v(i, j) = v 0(i, j). By the deﬁnition of a dynamic
grid quorum, v 0(i, j), v 0(j, i) ∈ Q0R , because Q0R has
the corresponding diagonal node if Q0R has a node in
the left-side exchangeable area. On the other hand,v(i, j) ∈ QW . Thus QW ∩ Q0R 3 v(i, j).
Case (c): Because v 0(i,j) is never exchanged, v(i,j) =0v (i,j). Thus QW ∩ Q0R 3 v(i, j).
ut
We note that this proposition also guarantees that
our reconﬁguration can be done without any data migration to preserve the consistency of replicated data.

Example 4
Let us consider a system consisting of
4 × 4 grid, whose initial allocation is v0 . Now we assume that the system load for both write and read requests is 2, and the capacity of every node is 4. In thiscase, to minimize power consumption, the best strategy is to gather all the write requests to the write quorum QW = {u1 , u2 , u3 , u4 } (i.e., the quorum consisting of the leftmost column) and all the read requests
to the read quorum QR = {u4 , u8 , u12 , u16 } (i.e., thequorum consisting of the lowest row). As the upper
system in the ﬁgure indicates, with this strategy thethree nodes {u1 , u2 , u3 } are used for write operations,the three nodes {u8 , u12 , u16 } are used for read operations, and the node u4 is used for both. Thus, the total
number of active nodes is 7. Here we consider the two
distinct allocations, vW and vR , to reconﬁgure the writeφE0

and read quorums, where v0 −→ vW and v0 −→ vR with
E 0 = {u1 , u2 , u3 }. The result is presented in the lower
two systems in the ﬁgure. As this indicates, because
only QR is changed to {u1 , u2 , u3 , u4 } from {u4 , u8 , u12 ,u16 }, after the reconﬁguration, both QW and QR consist of the same nodes {u1 , u2 , u3 , u4 }. Thus, the number of active nodes becomes 4.
The formal deﬁnition of the dual allocation is asfollows.
Definition 3 (Dynamic grid quorum with dual
allocation) For any initial allocation v0 and degree
f , let hvW , vR i be a pair of (possibly diﬀerent) allocations ranging over the same nodes and satisfying thefollowing condition:

6vW
for any write/read quorums QW , Q0W ∈ CW
and forvR
any QR ∈ CR , QW ∩ QR 6= φ and QW ∩ Q0W 6= φhold. The former one follows from Proposition 1 andthe deﬁnition of dual allocation, while the latter one
from the deﬁnition of dynamic grid quorum. Moreover,
the reconﬁgurations for the dynamic grid quorum withdual allocation also preserve the one-copy serializability. This can be shown by Proposition 1.
In the next section, throughout we consider the dual
allocation.

7 Optimization Algorithm
Our idea for power optimization is to skew the load
towards a small number of quorums. This is realizedby our optimization algorithm which is introduced below. To make our discussion simpler, we consider thefollowing restrictions throughout this section.
f(R1) For any (i, j), (i, j 0 ) ∈ Eleft,cap(v0(i, j)) = cap(v0(i, j 0 )).

Fig. 4 Example of dual allocation (with E 0 = {(1, 2), (1, 3),(1, 4)})
E0

f
There exist E 0 , E 00 ⊆ Eleftsuch that v0 −→ vW andE 00

v0 −−→ vR .
We call this pair a dual allocation. A dynamic gridvW ,fquorum with dual allocation hvW , vR i is a pair hCW
,
v,f
vR ,f
,
i of collections of node groups obtained from hCW
CR
v,f
vW ,f
CR
i by replacing v with vW (to determine CW
) and
vR ,f
vR (to determine CR), in Deﬁnition 1.
ut
Clearly, for any dual allocation, vW can be obtained
from vR by reconﬁgurations and vice versa. In addition,
any dynamic grid quorum deﬁned as Deﬁnition 1 is a
special case of a dynamic grid quorum with dual allocation such that vW = vR .
We can naturally extend the deﬁnition of reconﬁguration for a dynamic grid quorum (presented in Deﬁnition 1) to the one with dual allocation by separately
considering the allocations for write and read operations. The related notions can be deﬁned in a similar00
way. We say that v 0 = hvW, vR
i is a reconﬁgured dual
allocation obtained from v = hvW , vR i, if there exist
E0

E 00

0
0
E 0 , E 00 ⊆ Eleft such that vW −→ vW
and vR −−→ vR.
hE 0 ,E 00 i

The notation v −−−−−→ v 0 is used to represent that v 0
is obtained from v by reconﬁguration.
We note that, in our deﬁnition of dynamic grid quorum with dual allocation, the one-copy serializability
still holds. To guarantee this consistency, it is suﬃcient
to show that for any dual allocation v = hvW , vR i andf(R2) For any (i, j), (i0 , j) ∈ Elow,cap(v0(i, j)) = cap(v0(i0 , j)).

(R3) If there exists (i, j) with On(v0(i, j)) = 1 thenOn(v0(i, j 0 )) = 1 for any j 0 ≤ j.
(R4) If there exists (i, j) with loadW (vW (i, j)) 6= 0
then On(vW (i0 , j)) = 1 for any i0 ≤ i.
f(R5) For any (i, j), (i, j 0 ) ∈ Eleft, vW , and E 0 such
E0

that v0 −→ vW , if (i, j) ∈ E 0 then (i, j 0 ) ∈ E 0 .
f(R6) For any (i, j), (i0 , j) ∈ Eleft, vR , and E 0 such thatE0

v0 −→ vR , if (i, j) ∈ E 0 then (i0 , j) ∈ E 0 .
Intuitively, (R1) and (R2) respectively represent
that in the left-side and in the lower exchangeable areas, the capacity of any node in the same column andin the same row is the same for the initial allocation.
(R3) and (R4) respectively represent that if there is anactive node, then all nodes below this node in the same
column and all nodes in the same row on the left of thisnode are also active for the initial allocation and for any
write allocation. (R5) and (R6) respectively represent
that reconﬁgurations for any write and read allocations
simultaneously exchange all the exchangeable nodes on
the left in the i-th column, with the corresponding diagonal nodes.
Under these restrictions, we consider the following
problem.
Problem 1 For a given initial allocation v0 , a degree
f , a capacity cap, and a system load ld, ﬁnd a pair ofa strategy P and a reconﬁgured dual allocation v thatminimizes the power consumption of the system.

7

Our optimization algorithm (called OA), includes
the sub-algorithm (called SA), where algorithm SA isused to ﬁnd an optimal strategy for a given allocationand system load. By means of SA, algorithm OA ﬁnds
an optimal solution to Problem 1 among all the possible pairs each of which consists of a reconﬁgured allocation from the initial allocation and its optimal strategy.
More precisely, our algorithm solves the problem by thefollowing procedure.
First, for a given initial allocation v0 and a given system load ld, algorithm OA considers all the possible reconﬁgured allocations obtained from v0 . Then, for eachof these allocations, algorithm SA checks all the possible state-functions one-by-one to ﬁnd one which minimizes power consumption and does not overload thesystem. From this optimal state-function, SA ﬁnds an
optimal strategy which minimizes power consumption
for this allocation by using linear programming. Here
we would like to note the following point about the computational complexity. In general, the number of statefunctions increases exponentially with the number ofnodes in the system. Thus, to improve the problem ofthis search space explosion, algorithm SA checks thestate-functions in ascending order of power consumption with a pruning technique. In addition, when using
linear programming to ﬁnd an optimal strategy, anotherproblem of search space explosion emerges. That is, thenumber of quorums generally increases exponentiallywith the number of nodes, so this results in an explosion of the search space for this optimization. On theother hand, the power consumption of the system is determined only by the total load of each node. From thisobservation, the key idea in optimizing the strategy is
to divide each quorum into its components and consider
only the loads of each component. Then we can limit
the search space to a subset created from a special typeof load, called component load, from which we obtainour desired strategy.
Next, for a given set of pairs of reconﬁgured allocations from v0 and their optimal strategy (which is
obtained by the previous step), algorithm OA ﬁnds an
optimal pair, namely a solution to Problem 1. In thisstep, since the number of allocations increases exponentially with the value of degree for columns c, the computational complexity of this step also increases exponentially with c. To address this problem, our algorithm
also uses a pruning technique.
Here P opt and v opt are used respectively to denotethe strategy and the allocation obtained by our algorithm OA. Then the following theorem holds.

The outline of the proof of Theorem 1 is as follows. For the preparation, we ﬁrst deﬁne the component
load. Next, we prove Lemmas 1 and 2 which guaranteethat an optimal strategy can be obtained from an optimal component load. Then we prove Lemma 3, which
conﬁrms that we can ﬁnd an optimal component load,
if any, for a given allocation. Furthermore, we prove
Lemma 4, which conﬁrms that we can ﬁnd an optimal
pair of a component load and a reconﬁgured allocationfrom the initial allocation. Finally, we prove Theorem
1 by using Lemmas 1–4.
Definition 4 (Component load) For a given dual
allocation v, a degree f and system load ld, we deﬁnecomponent load consisting of the following ﬁve functions:– c-loadWN : VW ×{(i, j) | (i, j) 6∈ Eleft ∧1 ≤ i < n} → R+,– c-loadWT : VW × T → R+ ,– c-loadWC : VW × {i | 1 ≤ i ≤ n} → R+ ,– c-loadRN : VR × {(i, j) | (i, j) 6∈ Eleft } → R+ ,– c-loadRT : VR × T → R+ .
Here VA is the set of write/read allocations; R+ is theset of non-negative real numbers; T is the set of tuplesof natural numbers (each of which is denoted by t =ht1 , t2 , . . . , tc i) deﬁned as follows:– ti ∈ {0} ∪ {j | (i, j) ∈ Eleft };– If 0 < ti = j ≤ c for some j, then tj = 0 for any i;– If 0 < ti = j for some j, then ti0 6= j for any i 6= i0 .
In addition, c-load previously deﬁned satisﬁes conditions (6) to (13) given below.
n∑–c-loadWC (vW , i) = ldW .
(6)
i=1

–

m
∑

n
∑

c-loadWN (vW , (i, j)) =c-loadWC (vW , i0 )

i0 =i+1

j=1

for any i (c < i < n). (7)∑–c-loadWT (vW , t) =∑c-loadWC (vW , i).

(8)

i=m+1

t∈T

–

n
∑

c-loadWT (vW , t) =t∈T,ti =0∑c-loadWN (vW , (i, j)) −(i,j)6∈Eleftr−1∑c-loadWC (vW , i0 )

i0 =i+1

for any i (1 ≤ i ≤ c). (9)–∑c-loadWT (vW , t) ≤ c-loadWN (vW , (i, j))t∈T,ti =j

Theorem 1 The pair of P opt and v opt is an optimal
solution to Problem 1.

for any i (1 ≤ i < n). (10)

8

–

∑

c-loadRT (vR , t) = ldR .

(11)

t∈T

–

∑

c-loadRT (vR , t) =∑c-loadRN (vR , (i, j))for any i (1 ≤ i ≤ n). (12)∑c-loadRT (vR , t) ≤ c-loadRN (vR , (j, i))t∈T, ti =j

for any (i, j) ∈ Eleft .

(13)
u
t

The intuitive meaning of this deﬁnition is as follows.
First, to consider the write load of components, we divide each write quorum into the following three components: (a) the set of nodes on Col(i), (b) the set ofnodes on the left-side exchangeable points, and (c) theother nodes. The loads of components (a) and (c) arerepresented by c-loadWC and c-loadWN , while the loadof component (b) is represented by c-loadWC (vW , i) (inthe case of i ≤ m) or c-loadWT (vW , t) (in the case ofi > m). That is, in the case of i > m, ti is included int iﬀ node vW (i, j) is included in the components withti = j.
On the other hand, to consider the read load of components, we divide each read quorum into the following
two components: (d) the set of nodes on the left-side
exchangeable points and (e) the other nodes. Functions
c-loadRT and c-loadRN represent the total loads of (d)and (e). Vector t in c-loadRT indicates a component of(e), namely ti is included in t iﬀ node vR(i, j) is includedin the components with ti = j.
Instead of loadW and loadR (introduced by Eq. (2)),
in terms of the ﬁve functions introduced by Deﬁnition
4, we deﬁne c-loadA : V × U → R+ (where V is the setof dual allocations) that represents the total write/readload of each node, as follows.
– c-loadW (v, vW (i, j)) =c-loadWC (vW , i) + c-loadWC (vW , j)


∑



+ t∈T, ti =j c-loadWT (vW , t)
if (i, j) ∈ Eleft (14)
c-loadWC (vW , i) + c-loadWN (vW , (i, j))otherwise.

– c-loadR(v, vR(i, j)) = ∑c-loadRT (vR , t) if (i, j) ∈ Eleftc-load(v, u) = c-loadW (v, u) + c-loadR(v, u).

(i,j)6∈Eleftt∈T, ti =0–

As in the case of function load, we also deﬁne c-load as
follows.

(15)t∈T, ti =jc-loadRN (vR , (i, j))otherwise.

For readability, throughout this paper we may omit theﬁrst parameter of c-loadA and c-load, if it is clear fromthe context.
In terms of the deﬁnition of c-load, instead of load
we can also deﬁne the same condition of the capacity
as Eq. (4) as well as the state-function as follows.
– c-load(u) ≤ cap(u)for any u ∈ U .

(16)– If c-load(u) 6= 0 then On(u) = 1
for any u ∈ U .

(17)

We now introduce Lemmas 1 and 2. For readability,
we consider the collection CW,Col(k) (k ≤ n) of write
0
quorums and functions πA and πA
as follows.
– CW,Col(k) = {QW | QW ∈ CW ∧∀j ≤ m (vW (k, j) ∈ QW )}for any k ≤ n.
– πA(t) = {QA | QA ∈ CA ∧ (ti = j 6= 0
iﬀ vA(i, j) ∈ QA ∧ (i, j) ∈ Eleft )∧∀k ≤ m(QA 6∈ CW,Col(k) )}for any t ∈ T.
0
– πA
(QA ) = ts.t. QA ∈ πA(t) for any QA ∈ CA

except for QA ∈ CW,Col(k) for some k ≤ m.
Intuitively, CW,Col(k) means the collection of write quorums each of which includes all the nodes in the k-th
column for the write allocation. Function πA(t) returns
the set of quorums whose components are indicated by0
input t, while πA
is similar to the inverse of πA .
Lemma 1 For any allocation v, any degree f , anysystem load ld, any capacity cap, and any component
load c-load satisfying (16), we can obtain a strategy Psuch that it satisﬁes (4) and its power consumption is
the same as c-load.
Proof To show this lemma, it is suﬃcient to show that
loadW (u) = c-loadW (u) and loadR(u) = c-loadR(u) for
any u ∈ U . To obtain these equations, we deﬁne PW
and PR as (18) and (19), respectively.

9– PW (QW ) =0c-loadWC (vW, k)·c-loadWT (vW, πW
(QW))

∑
·g1(QW)nldW · k0 =m+1 c-loadWC (vW , k 0 )for some k > mc-loadWC (vW , k)
· g1(QW )



ldW


otherwise
where k satisﬁes QW ∈ CW,Col(k) . (18)0
(QR ))
c-loadRT (vR , πR
– PR(QR ) =· g1(QR ).
ldR∏(i,j)∈E 0

QW 3vW (i,j),QW 6∈CW,Col(i)∑– c-loadWT (vW , t) =loadW (QW ).

(22)

QW ∈πW (t)

(19)

∑

– c-loadWC (vW , i) =Here g1 is deﬁned as follows.
g1(QA ) =Proof To show this lemma, it is suﬃcient to show thatc-loadW (u) = loadW (u) and c-loadR(u) = loadR(u) for
any u ∈ U , where loadW and loadR are determinedby P . To obtain these equations, we deﬁne c-loadWN ,c-loadWT , c-loadWC , c-loadRN , and c-loadRT as (21),(22), (23), (24), and (25), respectively.
∑– c-loadWN (vW , (i, j)) =loadW (QW ).(21)loadW (QW ).

(23)

loadR(QR ).

(24)

QW ∈CW,Col(i)g2(i, j)∑g2(i, j 0 )∑– c-loadRN (vR , (i, j)) =(i,j 0 )6∈Eleft

QR 3vR (i,j)

for i 6= k if A = W,
where E 0 = {(i, j) | vA(i, j) ∈ QA ∧ vA(j, i) 6∈ QA }, andk satisﬁes QW ∈ CW,Col(k) . In addition, g2 is deﬁned asfollows.
g2(i, j) =c-loadAN (vA , (i, j)) −∑c-loadAT (vA , t).

t∈T, tj =i

Then by the deﬁnitions of c-load (i.e., Eqs. (6)–(10), we
can derive the following equation from (18).
∑PW (QW ) · ldW =– c-loadRT (vR , t) =∑loadR(QR ).

(25)

QR ∈πR(t)The equation c-loadW (vW (i, j)) = loadW (vW (i, j))can be obtained by (22) and (23) for any (i, j) ∈ Eleft .
In addition, the same equation can be obtained by (21)and (23) for any (i, j) 6∈ Eleft .
Similarly, we can also derive c-loadR(vR(i, j)) =loadR(vR(i, j)) for any (i, j) from (24) and (25).
ut

Next, we introduce algorithm SA presented in Fig.
5. For any allocation, any degree, any system load, andany capacity, this algorithm ﬁnds a component load, if
QW 3vW (i,j)
any, which minimizes power consumption among all thecomponent loads satisfying (16) and (17).
c-loadWC (vW , i) + c-loadWC (vW , j)∑
The algorithm SA consists of three sub-algorithms+ t∈T, ti =j c-loadWT (vW , t)
named LP1, LP2, and LP3, which are based on linear
if (i, j) ∈ Eleft programming. For given k, i ≤ n, LP1 and LP2 re
spectively estimate the lower- and upper-bound of thec-loadWC (vW , i) + c-loadWN (vW , (i, j))
number of active nodes in the i-th column for read allootherwise.
cations such that the system is not overloaded with the(20)
nodes up to the k-th column (i.e., loadW (vW (k 0 , j)) = 0
for all k 0 > k and for all j). That is, the outputs of LP1
Hence, from (14), which is the condition of c-loadW , and(20), we can obtain loadW (vW (i, j)) = c-loadW (vW (i, j)) and LP2 are deﬁned as follows.
for any (i, j).
– LP1(i, k) = min{j |Similarly, we can also derive loadR(vR(i, j)) =∑0
j 0 ≤j cap(vR (i, j )) ≥ ldR + min L(i, j)},c-loadR(vR(i, j)) from (11)–(13), (15), and (19).
ut
In addition, the following lemma, which is the converse of Lemma 1, is provable.

Lemma 2 For any allocation v, any degree f , anysystem load ld, any capacity cap, and any strategy P ,we can obtain a component load whose power consumption is the same as P .

– LP2(i, k) = min{j |∑0j 0 ≤j cap(vR (i, j )) ≥ ldR + max L(i, j)},where
L(i, j) is the set of all possible values of∑0
j 0 ≤j c-loadW (vW (i, j )) such that c-loadW satisﬁes
0 0
c-loadW (vW (i , j )) = 0 for any i0 > k and for any j 0 .

10Here each element of L(i, j) means the total write loadof nodes below the j-th row and in the i-th column. The
values of min L(i, j) and max L(i, j) can be solved using
linear programming whose constraints are represented
by the following conditions.
– Eqs. (6)–(13).
– For any i > k and for any j, c-loadW (vW (i, j)) = 0.
On the other hand, for given k and state-function, LP3
returns a component load, if any, satisfying the following conditions.
– Eqs. (6)–(13) and (17).
– For any i > k and for any j, c-loadW (vW (i, j)) = 0.
By using these sub-algorithms, SA ﬁnds an optimal state-function among the set S = ∪nk=0 Sk of statefunctions such that each On ∈ Sk satisﬁes the following
conditions.
(P1) On(vW (k 0 , j)) = 1 for any j and any k 0 ≤ k, andOn(vW (k + 1, j)) = 0 for some j.
(P2) For any (i, j), On(vR(i, j)) = 1 if j ≤ LP1(k, i).
(P3) On(vR(i, j)) = 0 for any (i, j) satisfying the following conditions:(P3.1) j > LP2(k, i),(P3.2) (i, j) 6∈ Elow or On(vR(j, i)) = 0,(P3.3) On(v0(i0 , h)) = 0 for any h > j 0 with v0(i0 , j 0 )= vR(i, j),(P3.4) i0 > k with vW (i0 , j 0 ) = vR(i, j).
(P4) On(vR(i, j)) = 1 for any (i, j) and (i0 , j 0 ) satisfying the following six conditions:(P4.1) i, i0 > k,
(P4.2) (i, j), (i0 , j 0 ) ∈ [r, m] or (i, j), (i0 , j 0 ) 6∈ [r, m],(P4.3) On(vR(i0 , j 0 )) = 1,
(P4.4) (i0 , j 0 ) 6∈ Elow or On(vR(j 0 , i0 )) = 0,(P4.5) On(v0(h, l0 )) = 0 for any l0 > l with v0(h, l) =vR(i0 , j 0 ),∑∑(P4.6) j ≤ min{h | h0 ≤h cap(vR(i, h0 )) ≥ l<j 0cap(vR(i0 , l))}.
To ﬁnd an optimal state-function, the execution processof SA is as follows.
Step 1: Find α such that for any k < α, LP3 has no
solution for Onall and k, where Onall is the statefunction with Onall(u) = 1 for any u ∈ U .
Step 2: For each Sk with k ≥ α, ﬁnd On ∈ Sk suchthat |On| is the minimum among all state-functions
which do not cause system overload.
Step 3: If the power consumption of every state-function in Sk+1 is more than the one of state-function
On such that |On| is the minimum for all the functions found in Step 2, then return On. (We call this
output Onopt .)1:input: U, v, E f , cap, ld
2:Onopt ← U ;3:k ← 0 ;4:while LP3(α, Onopt ) returns no strategy
5: if k = n thenexit “NO SOLUTION” ;6:
7: k ← k + 1 ;8:loop9: On ← {vW (i, j) | i ≤ k} ;10: On ← On ∪ {vR (i, j) | j ≤ LP1(i, k)} ;11: loopOn0 ← On ∪ {v0(i, j) | ∃i0 (v0(i0 , j) ∈ On ∧ i < i0 )} ;12:
On0 ← On0 ∪ {vR (i, j) | vR (j, i) ∈ On ∧ (j, i) ∈ Eleft } ;13:
if On = On0 then14:
break ;
15:
On ← On0 ;16:
17: if |On| ≥ |Onopt | thenreturn LP3(n, Onopt ) ;18:
19: S ← {On} ;20: while S 6= φ
On ← arg min{|On0 | | On0 ∈ S} ;
21:
On0

22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:

if |On| ≥ |Onopt | thenbreak ;
if LP3(n, On) thenOnopt ← On ;break ;
for i = 1 to n
On0 ← On ∪{vR (i, j) | j = max{j 0 | vR (i, j 0 ) ∈ On}+1} ;loop
On0 ← On ∪ {v0(i, j) | ∃i0 (v0(i0 , j) ∈ On ∧ i < i0 )} ;On0 ← On0 ∪ {vR (i, j) | vR (j, i) ∈ On ∧ (j, i) ∈ Eleft } ;add nodes to On0 for satisfying (P4) ;if On = On0 thenbreak ;On ← On0 ;if |On| < |Onopt | and On satisﬁes (P4) thenS ← S ∪ On ;if k = n thenreturn LP3(n, Onopt ) ;k ←k+1 ;Fig. 5 Algorithm SA

Clearly, when algorithm SA terminates, |Onopt | ≤|On| for any On satisfying that On ∈ Sα ∪ · · · ∪ Sn .
Now we show that algorithm SA ﬁnds an optimalcomponent load for a given system setting and its load.
Lemma 3 For any allocation v, any degree f , anysystem load ld, and any capacity cap, algorithm SA returns a component load, if any, which minimizes power
consumption.
Proof To show this lemma, it is suﬃcient to show thefollowing properties hold.
(C1) For any k < α and for any On ∈ Sk , On causes
the system overload.
(C2) For any On 6∈ S, On causes the system overload
or |On| ≥ |Onopt |.

11

41:input: U, v0 , E f , cap, ld
42:C ← φ ;43:Onopt ← U ;44:S ← {hK0W , KW R i | K0W , KW R ⊆ {1, . . . , c}} ;45:while S 6= φ
46: s ← some element chosen from S ;47: S ← S − {s} ;48: v ← the allocation made by s from v0 ;49: C 0 ← SA(U, v, E f , cap, ld) ;50: On ← the set of active nodes determined by C 0 ;51: if |On| < |Onopt | thenC ← C0 ;52:
v opt ← v ;53:
Onopt ← On ;54:
if |Onopt | < m2 then55:
S ←S−R ;56:# R is the set of allocations satisfying condition (P5).
57:
58:Transform C into strategy P opt by using Eqs. (18) and (19) ;59:return v opt , P opt ;any system load, and any capacity, this algorithm ﬁrst
ﬁnds an optimal pair of a component load and a reconﬁgured allocation (up to line 58) then returns a solution
to Problem 1 by transforming this component load into
an optimal strategy with Eqs. (18) and (19). Clearly, we
can ﬁnd an optimal pair of an allocation and a component load by considering all the possible reconﬁgured
allocations and then checking them one-by-one using
algorithm SA. However, as mentioned before, to reducethe computational complexity of this procedure, we use
the pruning technique as follows.
For any initial allocation v0 and for any allocation
hvW , vR i, let K(v0 , vW ) and K(vW , vR ) be sets of indexes of columns, satisfying the following conditions.
∪E0– v0 −→ vW s.t. E 0 =(Col(k) ∩ Eleft ) .
k∈K(v0 ,vW )Fig. 6 Algorithm OA
E 00

For (C1): We assume that there exists On ∈ Sk forsome k < α such that LP3(On, k) (i.e., the output of
LP3 for the inputs On and k) is component load c-load.
Then c-load clearly satisﬁes (17) with Onall . Thus, Step
1 of SA ﬁnishes with this k. This contradicts k < α.
For (C2): It is suﬃcient to show that for any statefunction On 6∈ S, if LP3(On, n) has a solution (where nis the number of columns in the system) then there exists a state function On0 ∈ S such that LP3(On0 , n)
has a solution with |On0 | ≤ |On|. For space limitations, we show only the case that On does not satisfy (P4). That is, we assume that there exist (i, j) and(i0 , j 0 ) satisfying (P4.1)–(P4.6) with∑mOn(vR(i, j)) = 0.
By∑
(P4.1) and (P4.2), we obtain j=1 loadW (vR(i, j))m= j=1 loadW (vR(i0 , j)). In addition, by (P4.6), we ob∑j 0 −1
∑j−1
tain h=1 cap(vR(i, h)) < h=1 cap(vR(i0 , h)). Thus,by the assumption On(vR(i, j)) = 0,0j∑−1

cap(vR(i0 , h))

h=1

≥

m
∑

c-loadW (vR(i0 , h)) + ldR .

(∗)

h=1

Let On0 be a state-function such that On0(vR(i0 , j 0 )) =0 and for any node u except for vR(i0 , j 0 ), On0(u) =On(u). For this state-function, from (P4.4), (P4.5), andinequation (∗), we can conclude that LP3(On0 , k) has
a solution. Clearly, since On0(vR(i0 , j 0 )) = 0, (P4.3)
is false, thus On0 satisﬁes (P4). Therefore, On0 ∈ S.
Moreover, |On0 | < |On|, because On0(vR(i0 , j 0 )) = 0
while On(vR(i0 , j 0 )) = 1 and On0(u) = On(u) with
u 6= vR(i0 , j 0 ).
ut
Next, we introduce algorithm OA, which is presented
in Fig. 6. For any given initial allocation, any degree,– vW −−→ vR s.t. E 00 =∪(Col(k) ∩ Eleft ) .

k∈K(vW ,vR )Note that, by (R5) and (R6), it is guaranteed that there
exist such K(v0 , vW ) and K(vW , vR ) for any v0 and
hvW , vR i.
In the procedure to ﬁnd an optimal pair of a component load and a reconﬁgured allocation from v0 , atlines 55 and 56 in Fig. 6, if it is known that the numberof active nodes of this solution is the same or smaller
than m2 (where m is the number of rows in the system), algorithm OA omits the allocations, whose set isdenoted by R, such that each v ∈ R satisﬁes the following condition.
(P5) There exists (i, j) ∈ Eleft such that (i, j) and v =hvW , vR i satisfy both (P5.1) and (P5.2) below.
(P5.1) cap(vW (i, j)) < cap(vW (j, i)), i 6∈ K(v0 , vW ),and i ∈ K(vW , vR ).
(P5.2) At least one of the following conditions (P5.21) and (P5.2-2) is satisﬁed.
(P5.2-1) There exists i0 such that i < i0 andi0 ∈ K(v0 , vW ).
(P5.2-2)
holds:∑c The following inequation00max{cap(v
(i
,
j)),
cap(v
0
W
W (j, i ))} <
i =1
ldR .
Note that for any system in which the number ofcolumns is the same or smaller than the one of rows
(i.e., n ≤ m), the number of active nodes of an optimal
solution is always the same or smaller than m2 .
Even though there is such a reduction of search
space, algorithm OA ﬁnds an optimal solution. Thatis, the following lemma holds.
Lemma 4 For any initial allocation v0 , any degree f ,any system load ld, and any capacity cap, we can obtain

12

a pair of a component load and a reconﬁgured allocationfrom v0 , if any, which minimizes power consumption.
Proof To show this lemma, it is suﬃcient to show thatfor any allocation v ∈ R, if there is a component loadc-load such that the power consumption determined byc-load is the same or smaller than m2 and the pair of v
and c-load is optimal for the given f , ld, and cap, thenthere exists an allocation v 0 6∈ R such that the pair ofv 0 and c-load is also optimal.
For space limitations, we show only the case thatv satisﬁes (P5.2-1). That is, there exist (i, j) ∈ Eleftand i0 such that (i, j), i0 , and v satisfy both (P5.1) and(P5.2-1). Here we consider the following two cases: (a)c-loadWC (vW , i00 ) = 0 for any i00 ≥ i0 , and (b) otherwise.

Finally, we prove the main theorem below.
Proof (Proof of Theorem1) Let hc-load opt , v opt i be thepair of the component load and the reconﬁgured allocation obtained by algorithm OA. Then, by Lemma 4, thispair is an optimal one in the set of all the pairs of component loads and allocations. Thus, by Lemma 1, we
can obtain a strategy P opt whose power consumption
is the same as c-load opt . Moreover, P opt is an optimal
strategy for v opt , because if there exists another strategy whose power consumption is smaller than that ofP opt , then by Lemma 2, a better solution also exists
in the set of component load for v opt . This contradicts
Lemma 3.
ut

hE 0 ,φi00
For (a): We deﬁne v 0 = hvW, vRi as v −−−−→ v 0000
where E = Eleft ∪Col(i ). Then v 6∈ R. By the assumption, as the power consumption of c-load is the same orsmaller than m2 , we obtain c-loadWT (vW , t) = 0 for
any t ∈ T . Since c-loadWC (vW , i00 ) = 0 for any i00 ≥ i0 ,c-loadWC (vW , i0 ) = 0. Hence, c-loadW (v, vW (i0 , j 0 )) =c-loadW (v 0 , vW (i0 , j 0 )) = 0 for any j 0 with (i0 , j 0 ) ∈ Eleft .
Thus, for any u ∈ U , the load of u determined by c-loadis the same for both v and v 0 for the given f , ld, cap.
Therefore, the pair of v 0 and c-load is also optimal.
hE 0 ,φi00
For (b): We deﬁne v 0 = hvW, vRi as v −−−−→ v 00where E = Eleft ∪ Col(i). Then the following equation
holds.

c-load(v 0 , v0(h, l)) =
c-load(v, v0(h, l)) − c-loadW (v, v0(h, l))





for h = i ∧ (h, l) ∈ Eleftc-load (v, v (l, h))
W

0







c-load(v, v0(h, l))for l = i ∧ (h, l) ∈ Elowotherwise.

Here, by (P5.1), (R1), and (R2) we obtain cap(v0(i, j 0 ))≤ cap(v0(j 0 , i)) for any j 0 with (i, j 0 ) ∈ Eleft . Thus,
as c-loadW (v, v0(i, j 0 )) ≤ cap(v0(i, j 0 )) for any j 0 with(i, j 0 ) ∈ Eleft , c-loadW (v 0 , v0(j 0 , i)) ≤ cap(v0(i, j 0 )).
Therefore, the pair of c-load and v 0 does not cause thesystem overload for the given f , ld, cap, and the allocation. Now we let On be the state-function determinedby c-load and v. Here the load of node v0(j 0 , i) with(j 0 , i) ∈ Elow may increase for c-load and v 0 , comparedwith the pair of c-load and v. However, On(v0(j 0 , i)) = 1
for any j 0 with (j 0 , i) ∈ Elow , because there exists i00 ≥i0 ≥ i with c-loadWC (vW , i00 ) 6= 0 and i0 ∈ K(v0 , vW ).
Thus, |On0 | = |On|, where On0 is the state-function determined by c-load and v 0 . Therefore, the pair of v 0 andc-load is also optimal.
ut

In closing this section, we present some remarks on
the restrictions considered in this section, the computational complexity of our algorithm, and implementationof our proposed system.
Remark 1 (Restrictions on the capacity and the state ofnodes) For simplicity in our discussion, we introduce
in this section some restrictions on the capacity and thestate of the nodes. However, if we disregard one of therestrictions (R1)–(R6), there may be a better solution
than that obtained by our algorithm.
Such an example is as follows. Let Onopt and c-loadbe the state-function and component load obtained byalgorithm OA for a given system and its workload. Then
let k be max{i | c-loadWC (i) 6= 0}. Now we consider astate-function On satisfying the following conditions.
– If Onopt(u) = 0 then On(u) = 0 for any u ∈ U ;– For any i 6∈ K(vW , vR ).
∑j∈{j 0 |On(vR (i,j 0 ))=1} cap(v(i, j)) ≥ ldR + LP2(i, k).
– For∑ any (i, j) ∈ Eleft , if On(vR(j, i)) = 0 thent∈T,ti =j c-loadRT (ti ) = 0.
In this case, the nodes, each of which u satisﬁes Onopt(u)= 1 and On(u) = 0 can be reduced if we disregard assumption (R3).
More concretely, (see Fig. 7 for the graphical presentation) let n = 4, m = 4, f = h0, 4i, ld = h0, 3i, andcap(v0(1, j)) = 2 for any 1 ≤ j ≤ 4, and cap(v0(i, j)) =4, otherwise. By (R3), the minimum set of active nodesis {v0(i, j) | 1 ≤ i ≤ 2 ∧ 1 ≤ j ≤ 4}, where the total
number of nodes is 8. Without (R3), however, nodes{v0(i, j) | i = 2 ∧ 1 ≤ j ≤ 4} are suﬃcient, giving a
total number of 4 nodes.

13Fig. 7 Active nodes of dynamic grid quorum with/without (R3)

Remark 2 (Computational complexity) As explained
before, to solve Problem 1 there are three factors causing an exponential increase in the computational complexity of the calculation, namely, the number of constraints used by the linear programming in SA, thenumber of state-functions treated by SA, and the number of reconﬁgured allocations treated by OA. In terms
of pruning techniques as well as the notional component
load, the computational complexity of our proposed algorithm is decreased. Indeed, as far as our experiments
are concerned, we can ﬁnd optimal solutions in a feasible time for all cases of the simulations in the next
section. However, these three factors may still cause asearch space explosion. The maximum values of thesefactors, say, ν1 , ν2 , and ν3 can be represented with the
O-notation as follows:– ν1 = O((m − r)c ),– ν2 = O((c − π)r + c · n · m),– ν3 = O(2c ).
Here, n, m, c, and r are the numbers of columns androws, and the degrees∑ for columns and0 rows, respectively; π = min{j | 0≤j 0 ≤j cap(vR(i, j )) ≥ ldR ∧ 1 ≤i ≤ n}. In terms of these values, for the worst case, therequired calculation to solve Problem 1 is the c·ν2 ·ν3 iterations of linear programming using ν1 constraints. A
possible way to avoid such exponential growth is to restrict c to a small number. On the other hand, (c − π)rin the second equation is feasible in most cases, because large ld keeps c − π small, and small ld makes theprobability of breaking into short loops high. Moreover,c · n · m in the second equation is also feasible, because
it is shortened by pruning by (P4) of SA in a practicalsense. This is a simple way to avoid the search space
explosion, but an improvement to our algorithm is stillneeded. This will be investigated in one of our futurestudies.
Remark 3 (Implementation) Finally, we make some
remarks related to the implementation of our proposedsystem. For implementation, ﬁrst, the information of
the current system load is needed to calculate optimal
storage. It can be obtained by observing nodes in at
most one column in read allocation and at most one row
in write allocation. That is, it is suﬃcient to observev0 (Col(i)) and v0 (Row(i)) for any i, where v0 is theinitial allocation.
Next, all the clients must share the allocation andstrategy, however, from Proposition 1, it is derived thatthe consistency of the data are guaranteed even if someclients are out of synchronization. Thus, although it
may cause temporarily high power consumption, it is
not necessary to enforce strict synchronization amongclients. Therefore, the overhead of updating the allocation and strategy will be small.
Finally, we point out that some methods are usable
for managing the power of each node. For example, byrestriction (R3), when node v0(i, j) must change stateto active, v0(i, j − 1) also changes state to active or isalready active. Thus, it is suﬃcient for each node to
manage the power of the above node. Therefore, clientsneed to manage the power of no more than m nodes.

8 Simulation Results
In the evaluation of this section, we consider the following four systems for a 10×10 grid: dynamic grid quorum
with dual allocation (DDG), dynamic grid quorum withno dual allocation (i.e., single allocation) (DG), andﬁxed allocation of nodes optimized for write requests(WG) and read requests (RG). First we evaluate theimpact of the write/read ratio for each case where thesystem load is low, medium or high. In contrast to theabove settings, we also evaluate the impact of the system load, where the write/read ratio is ﬁxed but the
total number of requests varies.
Parameters and Settings. Each system in the evaluation consists of 70 nodes with capacity a (for someconstant a) and 30 nodes with capacity 2a. In the WG
and RG, the nodes with 2a are allocated in Coli andRowi for 1 ≤ i ≤ 3, respectively. The DG is a dynamic
grid quorum with f = h3, 1i, while the DDG is a dynamic grid quorum with dual allocation with f = h3, 3i.
The reason we consider DG and DDG with diﬀerent
degrees is that DG with f = h3, 1i is better than thecase of f = h3, 3i with respect to the power consumption. To reduce the computational complexity, we consider the following restrictions (introduced in Section
7). The static systems WG and RG satisfy (R3) and(R4) while the dynamic systems DG and DDG satisfy(R1)–(R6). However, for DG, instead of (R3) we consider the restriction such that for any i < i0 and for14Fig. 8 Number of active nodes (ldW + ldR = 2.5a)Fig. 10 Number of active nodes (ldW +ldR = 7.5a)Fig. 9 Number of active nodes (ldW +ldR = 5a)Fig. 11 Number of active nodes (ldW : ldR = 1 : 3)

any j if On(vR(i0 , j)) = 1 then On(vR(i0 , j)) = 1. This
restriction reduces more power than in the case of (R3).
The initial allocation of DG and DDG is the same as
RG. For the impact analysis of the write/read ratio, we
use 2.5a, 5a, and 7.5a as the values for low, medium,and high loads in the system. This setting arises fromthe fact that the write and read capacity for a grid of
the same size, comprising homogeneous nodes with capacity a, is 10a and 6.5a, respectively. For the impact
analysis of the system load, we consider the write/readrequests to be 1/3, which is also used as the default
parameter in [16].
Impact of write/read ratio in the case of low
load. Fig. 8 shows that the power consumption of the
DDG is more stable over the range of the ratio of write
operations compared with the others. In addition, compared with the WG, RG, and DG, DDG saves on average 13.6%, 14.8%, and 4.3% respectively, for all ratios.
The results of this simulation show that dynamic grid
quorum with dual allocation reduces power consumption when compared with all the other systems, WG,
RG and DG.
Impact of write/read ratio in the case of medium
load. Fig. 9 shows that the DDG consumes more power
than the RG for the case of 0% of the write ratio andmore power than the WG above 90% of the write ratio.

However, except for these cases, the power consumption of the DDG is the least for all ratios. Considering more detailed results, the DDG saves on average
10.9%, 20.0%, and 12.5% compared with WG, RG, and
DG. The results of this simulation show that our system is also eﬃcient for a wide range of write ratios.
In addition, in this simulation, the DDG shows better
behaviour with a high write ratio than DG.
Impact of write/read ratio in the case of highload. Fig. 10 shows that the power consumption of the
DDG is the least for the range 10% to 50% of the write
ratio. The DDG consumes more power than the RG
for the case of 0% of the write ratio and more power
than the WG above 60% of the write ratio. However,a notable fact is that above 60% of the write ratio,
DDG is still eﬀective compared with RG and DG, while
DG cannot handle a write ratio above 70%. Comparedwith the WG and RG, DDG saves on average 6.4% and11.9%. Moreover, even if the write ratio is restricted in
the range 0% to 70%, DDG saves 14.9% compared with
DG.
Impact of load growth. Fig. 11 shows that the power
consumption of the DDG is the least for almost all of
the range for other system loads. Compared with the
WG, RG, and DG our system saves on average 25.2%,

1514.1%, and 10.6%. The results of this simulation showthat our system is eﬀective for any system load.

9 Conclusions and Future WorkIn this paper, we presented a power-aware quorum system called the dynamic grid quorum. To reduce power
consumption, the basic principle behind our system wasto skew the workload towards a small number of quorums, which was realized by the following techniques:reconﬁguration by exchanging nodes without data migration, dual allocation for write and read quorums, andan algorithm to ﬁnd an optimal pair for reconﬁgurationand its strategy for a given system setting and workload. We also evaluated our techniques by comparing
the proposed system using three alternatives, namely,
static write- and read-optimized conﬁgurations, and dynamic reconﬁguration with a single allocation. The result showed that our proposed system’s power savings
were, on average, between 10.6% and 25.2% with 1/3
write operation ratio.
There are several possible directions in which thiswork can be developed. From a theoretical viewpoint,
as mentioned in Section 7, we are interested in improving our algorithm to avoid the situation that results
in a search space explosion. In addition, we are interested in some extensions of our techniques, especially inmodeling the heterogeneity of power consumption andthe time required for the state transition of nodes, thatwere not considered in this paper. Furthermore, on apractical level, we plan to evaluate the eﬀectiveness of
our proposed techniques, which could be investigatedthrough a prototype implementation.
Acknowledgements This study was supported in part by the
Global COE Program on “Cybernics: fusion of human, machine,
and information systems.” This study was also partially supported through the SCOPE program by the Ministry of Internal
Aﬀairs and Communications of Japan.

References
1. Agrawal D, Abbadi AE (1991) An eﬃcient and fault-tolerant
solution for distributed mutual exclusion. ACM Trans on
Computer Systems, 9(1):1–20
2. Bernstein PA, Hadzilacos V, Goodman N (1987) Concurrency
Control and Recovery in Database Systems. Addison Wesley
3. Cheung S, Ammar M, Ahamad M (1992) The grid protocol:
A high performance scheme for maintaining replicated data.
IEEE Trans on Knowledge and Data Engineering, 4(6):582–
592
4. Colarelli D, Grunwald D (2002) Massive arrays of idle disks
for storage archives. Proc of the ACM/IEEE Conf on Supercomputing, pp 1–11

5. Frain I, Basmadjian R, Bahsoun JP, M’zoughi A (2006) How
to improve the scalability of read/write operations with dynamic reconﬁguration of a tree-structured coterie. Proc of the
Int Conf on Parallel Processing Workshops, pp 123–134
6. Fu A (1997) Delay-optimal quorum consensus for distributed
systems. IEEE Trans on Parallel and Distributed Systems,
8(1):59–69
7. Giﬀord D (1979) Weighted voting for replicated data. Procof the ACM Symposium on Operating Systems Principles, pp
150–162
8. Harnik D, Naor D, Segall I (2009) Low power mode in cloudstorage systems. Proc of IEEE Int Parallel and Distributed
Processing Symposium, pp 1–8
9. Ibaraki T, Kameda T (1993) A theory of coteries: Mutual
exclusion in distributed systems. IEEE Trans on Parallel andDistributed Systems, 4(7):779–794
10. Ishikawa M, Hasebe K, Sugiki A, Kato K (2009) Dynamic
Grid Quorum: A Novel Approach for Minimizing Power Consumption without Data Migration in Grid Quorums. IEEE
Int Conf on Service-Oriented Computing and Applications(SOCA’09), pp 142–149
11. Li D, Wang J (2004) EERAID: energy eﬃcient redundantand inexpensive disk array. Proc of the ACM SIGOPS European Workshop, 6 pages
12. Lin X (2004) Delay optimization in quorum consensus. Algorithmica, 38(2):397–413√
13. Maekawa M (1985) A n algorithm for mutual exclusion
in decentralized systems. ACM Trans on Computer Systems,
3(2):145–159
14. Peleg D, Wool A (1997) Crumbling walls: A class of practical and eﬃcient quorum systems. Distributed Computing,10(2):87–97
15. Pinheiro E, Bianchini R (2004) Energy conservation techniques for disk array-based servers. Proc of the Int Conf on
Supercomputing, pp 68–78
16. Pinheiro E, Bianchini R, Dubnicki C (2006) Exploiting redundancy to conserve energy in storage systems. Proc of thejoint Int Conf on Measurement and Modeling of Computer
Systems, pp 15–26
17. Tsuchiya T, Yamaguchi M, Kikuno T (1999) Minimizing the maximum delay for reaching consensus in quorumbasedmutual exclusion schemes. IEEE Trans on Parallel andDistributed Systems, 10(4):337–345
18. Wang J, Zhu H, Li D (2008) eRAID: Conserving energy inconventional disk-based raid system. IEEE Trans on Computers, 57(3):359–374
19. Weddle C, Oldham M, Qian J, Wang AI, Reiher P, Kuenning
G (2007) PARAID: A gear-shifting power-aware RAID. Procof the USENIX Conf on File and Storage Technologies, pp
245–260
20. Yao X, Wang J (2006) RIMAC: a novel redundancy-basedhierarchical cache architecture for energy eﬃcient, high performance storage systems. Proc of the ACM SIGOPS/EuroSys
European Conf on Computer Systems, pp 249–262
21. Zhu Q, Chen Z, Tan L, Zhou Y, Keeton K, Wilkes J (2005)
Hibernator: helping disk arrays sleep through the winter.
ACM SIGOPS Operating Systems Review, 39(5):177–190