Highly Available Primary-Backup Mechanism forInternet Services with Optimistic Consensus
Koji Hasebe, Naofumi Nishita, and Kazuhiko Kato
Department of Computer Science, University of Tsukuba
1-1-1 Tennodai, Tsukuba 305-8573, Japan
hasebe@cs.tsukuba.ac.jp, nishita@osss.cs.tsukuba.ac.jp, kato@cs.tsukuba.ac.jp

Abstract—We present an optimistic primary-backup (so-called
passive replication) mechanism for highly available Internet
services on intercloud platforms. Our proposed method aims at
providing Internet services despite the occurrence of a largescale disaster. To this end, each service in our method creates
replicas in different data centers and coordinates them with
an optimistic consensus algorithm instead of a majority-based
consensus algorithm such as Paxos. Although our method allows
temporary inconsistencies among replicas, it eventually converges
on the desired state without an interruption in services. In
particular, the method tolerates simultaneous failure of the
majority of nodes and a partitioning of the network. Moreover,through interservice communications, members of the service
groups are autonomously reorganized according to the type of
failure and changes in system load. This enables both loadbalancing and power savings, as well as provisioning for the
next disaster. We demonstrate the service availability provided
by our approach for simulated failure patterns and its adaptation
to changes in workload for load balancing and power savings by
experiments with a prototype implementation.

I. I NTRODUCTION
With the growth of cloud computing, Internet services
merged onto a common platform have become popular. In
recent years, the interoperability of clouds has been thoroughly
investigated to achieve higher levels of service that can copewith serious damage to a data center, provide computing power
for the real-time processing of large amounts of data, andrealize elastic management of huge computing resources.
In terms of the availability and fault tolerance of Internet
services, replication is a widely used approach. Despite thesimplicity of this technique, its implementation is complex
because replicating the service state on multiple physical nodes
requires that each replica remain synchronized and consistent
with the others. To realize consistency in replication, thewell-known primary-backup replication method (i.e., passive
replication) is often used [3]. In this model, one of the nodes(the primary) processes requests from clients and provides responses. The other nodes (backups) periodically receive stateupdate messages from the primary, allowing them to update
their state to match that of the primary. If the primary fails, oneof the backups is selected to take over as the new primary. In
implementing this technique, a consensus algorithm (see [4])is often used to reach agreement among all nodes regarding
which is the current primary and which update message is thelatest. A well-known consensus algorithm is Paxos [14]. Generally speaking, this algorithm guarantees that 2F + 1 nodes

will achieve consensus in an environment where up to F nodes
may simultaneously fail. However, if the majority of nodes
fail, the algorithm terminates without achieving consensus.
Thus, an implementation of primary-backup replication withsuch a majority-based algorithm cannot continue to provide
services if more than half of the nodes fail, for example, as theresult of a large-scale disaster. This limitation is, as Brewer’s
CAP theorem [1], [10] suggests, caused by the impossibilityof achieving both availability and consistency for services.
The objective of this research is to investigate a mechanism
to ensure high availability for Internet services based on the
primary-backup replication technique. In particular, the Internet service platform based on our proposed method aims toprovide services despite a simultaneous failure of the majority
of nodes and a partitioning of the network. To achieve this,
we take an alternative optimistic approach; instead of using amajority-based consensus algorithm, we use a modified Paxos
algorithm that allows agreement to be reached by fewer thanhalf of the nodes. Although this algorithm temporarily permits
an inconsistent situation (i.e., nodes may agree on different
states), it eventually reaches consistency even if a simultaneous
failure of the majority of nodes or a division of the network
occurs.
With this algorithm, the Internet services provided on thesystem avoid interruption by a large-scale disaster. Moreprecisely, a system based on our mechanism continues toprovide services as long as at least one node survives. Nevertheless, owing to the modification of Paxos, our system may
demonstrate illegal behavior at certain times. Typically, whena network partition divides into node groups consisting of a
primary and backups, one node becomes the primary in eachseparate subgroup, and there may be multiple primaries fora service. Thus, although our method cannot be applied to aservice that is required to maintain strict consistency, it is quite
useful for Internet services that require high availability but notstrict consistency, such as message boards for communication
during natural disasters.
Moreover, we incorporate a mechanism for load balancing
and the reduction of power consumption in the system. In
recent years, there have been a number of suggestions forachieving these goals in cloud data centers (see [2]). One key
idea commonly seen in the literature is to diffuse and skew thesystem’s workload according to its changes over time. Basedon this approach, in our method the members of a service

group are autonomously reorganized over nodes by migrating
stored data. This happens in accordance with changes in thesystem load.
In this paper, we also demonstrate availability through some
failure patterns and evaluate the effectiveness of the loadbalancing and power-saving mechanisms through experimentswith a prototype implementation.
The rest of the paper is organized as follows: Section
II discusses related work. Section III provides an overview
of Paxos and explains how we modify the algorithm. Section IV presents a system design using our method as a
typical application in an intercloud environment. Section V
describes our proposed primary-backup mechanism. Section
VI demonstrates service availability given various patterns offailure through simulations. Finally, Section VII concludes andrecommends future work.
II. R ELATED W ORK
Various techniques have been proposed to realize replication mechanisms, and these can be classified into two maincategories: state machine and primary-backup replication.
In state machine (i.e., active) replication [17], each node
processes requests from the clients and transitions independently. Generally, each transition is coordinated across thenodes by means of a consensus algorithm. Although thistechnique is useful, as a result of its low response time, it
has two significant drawbacks: there is a high computationalcost, and client requests must be processed in a deterministicmanner. On the other hand, primary-backup replication isuseful because of its low computational cost and applicability
to nondeterministic services. However, as mentioned in Section I, a mechanism is needed that allows agreement on thecurrent primary and its implementation; this is not necessary
in state machine replication systems. As explained above, themerits and demerits of these techniques are complementary.
To counter these drawbacks, some variant schemes have been
proposed in recent years. These include semiactive replication[18] and semipassive replication [6].
However, it is assumed that these techniques will employ
a majority-based consensus. Thus, although they guarantee
replica consistency, they cannot tolerate the simultaneous
failure of a majority of the nodes or partitioning of the
network. To address the issue of availability, Dolev et al.
[9] proposed optimistic state machine replication based ona self-stabilizing consensus algorithm [7], [8]. Subsequently,
Hasebe et al. [13] suggested a self-stabilizing primary backup
replication technique and its application to Internet service
platforms. The main motivation of our present study is todevelop a method for optimistic primary-backup replication
using a modified Paxos algorithm. We aim to apply this toInternet service platforms in which the replicas of each service
are placed in different data centers.
III. T HE PAXOS A LGORITHM AND M ODIFICATIONIn this section, we first provide an overview of the Paxos
algorithm [14] and then explain how to modify it to achieveconsensus even if fewer than half of the nodes survive.

(1) Request for
preparation(2) Ack/Nack(3) Propose(4) Ack/Nack(5) Decide

Node 1(Coodinator)
Node 2

Node 3Fig. 1.

Actions in each round in Paxos

A. Overview
Consensus is a fundamental problem in distributed computing. It is usually defined as the problem of achieving a goalin light of failures where nonfailed nodes, which started withdifferent inputs, decide on a common output value.
Paxos [14] is a well-known algorithm used to solve thisproblem. It proceeds in rounds and uses a rotating coodinator,i.e., a unique round number i is initially assigned to eachnode ni ∈ N = {n1 , . . . , nk } and then a node becomes thecoodinator based on its current round number. (A possible
way to determine the current coordinator is to choose thenoncrashed node with the smallest ID.) In each round, thecoodinator proposes a preferred value v as the candidate forthe output; if this is accepted by the majority of the nodes, thepreference is chosen and the algorithm terminates. Otherwise,
the coodinator increases its round number by N and switches
roles with another node. We note that the round number of
each node is uniquely determined at any time, but there may
also be multiple coodinators in the system. More precisely, theactions in each round consist of the following five steps (seeFig. 1 for illustration). For readability, we use pc and pa todenote the coodinator and the other nodes, respectively.
Step 1. pc sends a request for preparation of its roundnumber r, denoted by recP rep(r), to all the othernodes.
Step 2. If pa receives recP rep(r) and pa has sent Ack
to request recP rep(r′ ) or to request acceptance ofrecAccept(r′ ) with r′ > r, then it replies Nackto the request. Otherwise, it replies with the message Ack(r′′ , vprop (pa )), where vprop (pa ) is pa ’s
proposed value and r′′ is the round number inrecAccept(r′′ ) that was most recently accepted bypa . Here, if pa was never accepted, vprop and r′′ areset to Null and 0, respectively.
Step 3. pc waits to receive messages from at least half of thenodes (including itself). If the received messages include Nack , then pc terminates the round and increments r by N . If all the received messages are Ack,then pc sends the message recAccept(r, vprop (pc ))to the other nodes; here r is the round number ofthe current pc , and vprop (pc ) is pc ’s proposal.
Step 4. If pa receives recAccept(r) and it has sent Ack
to request recPrep(r′ ) or to request acceptance ofrecAccept(r′ ) with r′ > r, then it replies Nack to
the request. Otherwise, pa replies Ack to the request.

Cloud 1 (Crashed)

Cloud 2b1(s1) p(s1) b3(s3)Cloud 1Cloud 2b1(s1) p(s1) b3(s3)b1(s2)

b2(s1)b2(s2) p(s2)p(s3)

b3(s1)......

......

b2(s3)

1
1

n

1
2

n

1
3

Fig. 2.

n

1
k

n

2
1

n

2
2

n

2
3

n

2
k

1
1

p(s3)

b3(s2)......

b2(s3)p' (s1)b1(s2)nb2(s2) p(s2)b3(s1) b' (s ) b' (s )1 1 2 1......

b3(s2)

b1(s3)nb2(s1)

b1(s3)n1
2

nFig. 3.

1
3

n

1
k

n

2
1

n

2
2

n

2
3

n

2
k

System behavior after an entire data center fails

Overview of the system architecture

Step 5. pc waits to receive messages from at least half ofthe nodes (including itself). If the received messages
include Nack , then pc terminates the round and increments r by N . Otherwise, pc decides on vprop (pc )as the agreed value and terminates the procedure.
B. Modification of Paxos
As shown by [14], Paxos satisfies the following properties:
agreement (i.e., every noncrashed process must agree on thesame value), validity (the decided value is one of the inputs),
and termination (every noncrashed node eventually decides
on a value for output). On the other hand, because steps 3
and 5 require waiting for replies from at least half of thenodes, if a majority of them fail, the coodinator cannot proceed
to the next step and the algorithm does not terminate. This
limitation is unavoidable whenever the agreement property
holds, because if the coodinator node sends its proposedvalue before receiving messages from half of the nodes, there
may be multiple node groups deciding on different values.
In other words, guaranteeing agreement (i.e., consistency ofoutputs) and tolerating a majority of node failures is a trade-off
that is inherited from the development of the primary-backup
mechanism.
To increase the availability of a primary-backup mechanism,
our approach weakens the restrictions at steps 3 and 5, i.e.,
we modify the algorithm so that the coodinator can proposeor decide even if the number of received messages does notreach a majority. (However, to avoid frequent occurrences ofinconsistency among replicas caused by a temporary network
delay, setting a specific number of required messages thatshould be received by the coodinator is worthwhile.) Below,
we investigate a primary-backup mechanism based on thismodified algorithm and its applicability to Internet service
platforms.
IV. S YSTEM D ESIGN
Our proposed primary-backup mechanism is intended tobe applied primarily to Internet service platforms that are
deployed in data centers and clouds. Fig. 2 presents an
overview of the architecture of our target platform. Although
this platform is developed using a virtualization technique,this discussion is omitted to focus attention on the mechanism
itself.

To explain the central idea, we consider a simple example
that consists of two data centers, “cloud 1” and “cloud 2.”
The nodes in the two clouds are denoted by {ni1 , ni2 , . . . , niki }with i = 1, 2, and multiple servers coexist and provide Internet
services. Each service forms a group consisting of a primaryand some backups. (It is also possible that several nodes could
cooperate as a single primary.) In Fig. 2, we only illustrate
three groups for readability. Service s1 is provided by primaryp(s1 ) placed on node n12 in cloud 1, while p(s2 ) and p(s3 ), forservices s2 and s3 , respectively, are placed on n22 and n23 incloud 2. For each service, the required number of backups andthe conditions of their locations can be predetermined. In thiscase, we consider the requirement that every primary have atleast three backups, one of which is placed in a different cloud.
For example, p(s1 ) has three backups, i.e., b1 (s1 ) and b2 (s1 )placed on different nodes in cloud 1 and b3 (s1 ) in cloud 2.
When developing a new primary on a node, our mechanism
automatically invites nodes that can play a role in its backup.
In addition, if a node detects the failure of another node in
the same group, the remaining nodes tend to invite a newnode to take over for the missing backup and maintain therequirement. In each group, the primary periodically sends its
current service state to the backups, and if it fails, one of the
backups becomes the new primary and continues to provide
service. Owing to our consensus algorithm, services remain aslong as at least one node survives.
Fig. 3 illustrates the system behavior when a large-scaledisaster happens, i.e., all the nodes in cloud 1 have crashed.
In this case, the primary of service s1 is lost, and thus the
only surviving node, b3 (s1 ) on n21 , becomes the new primary[denoted by p′ (s1 ), enclosed by a bold rectangle in Fig. 3].
In addition, p′ (s1 ) asks n22 and n23 to take over the roles ofb′11 (s1 ) and b′21 (s1 ), respectively. Furthermore, this new nodegroup tends to invite another node from a different cloud totake over the role of b′31 (s1 ). Similarly, the groups for services
s2 and s3 complement its backup requirement in a different
cloud.
Fig. 4 shows the system’s behavior when the backbone
network between clouds 1 and 2 fails, making it impossible fornodes in different clouds to communicate. In this case, in eachcloud every separated node group considers all nodes in theother cloud to have crashed. Under our mechanism, in cloud 1,
b1 (s2 ) on n11 and b3 (s3 ) on n13 become primaries for s2 and s3and then complement their backups in the same cloud and indifferent clouds with which it can communicate; in cloud 2,

Cloud 1

Cloud 2b1(s1) p(s1) b3(s3)b1(s2)

p''(s3)b2(s1)b2(s2) p(s2)b3(s1)p(s3)......

b3(s2)......

b2(s3)

p''(s1)p''(s2)

disadvantage of this technique is a trade-off with disk space;however, if the system has enough storage and can afford
to create further redundancies, this technique can be usefulfor effective migration. (See also [12] for details of a similar
technique.)b1(s3)
1
n
1

1
n
2

1
n
3

1
n
k

n

2
1

n

2
2

n

2
3

n

2
k

Partitioned

Fig. 4.

System behavior after a network partition between clouds

Cloud 1Cloud 2b1(s1) p(s1) b3(s3)b1(s2)

b2(s1)b2(s2) p(s2)p(s3)

b3(s1)......

b3(s2)......

b2(s3)

b1(s3)

n

1
1

n

1
2

n

1
3

n

Fig. 5.

1
k

n

2
1

n

2
2

n

2
3

n

2
k

Off-peak system behavior

b3 (s1 ) on n21 becomes the primary for s1 and complements
its backups in a similar way. As this scenario indicates, a
network partitioning may lead to the existence of multiple
primaries for a service. Thus, each of the primaries provides
the same service independently, and the difference between
states will increase over time. During such a partition, eachnode group periodically tries to communicate with the othercloud. If the connection is restored, duplicated primaries merge
their states and one of them continues in the primary role while
the other disappears. Note that our mechanism allows multiple
primaries for a service, whereas in replication based on amajority consensus, all services would stop to strictly avoid
any inconsistency. In general, merging different states is adifficult task. However, in the case that a state changes only by
the appending of new data, as typified by an Internet message
board, the original state can be obtained with relatively little
effort.
So far, we have explained the mechanism for fault tolerance.
In a final example, we present the mechanism for load balancing and reducing the power consumption of a system. We
consider the allocation of primaries and backups as presented
in Fig. 2 and assume that the system workload is at peak-timelevels. If the load decreases and node n11 can take over therole of b3 (s3 ) on n13 without being overloaded, our mechanism
automatically moves the state stored by b3 (s3 ) from n13 to n11 ,thereby leaving n13 in a low-power mode (n23 can also be placed
into a low-power mode by migrating p(s3 ) to n22 ). When theload increases and a node becomes overtaxed, it relinquishes
some of its roles to another node with a lower workload.
Migration of a primary or backup burdens the system
network. To reduce the migration cost, retaining the data aftera migration for reuse when a primary or backup returns to
its original position is worthwhile. This enables migrationby copying the difference from the previous migration. The

V. A LGORITHMS
Our primary-backup mechanism consists of the following
six algorithms:
1) Failure detection2) Group reorganization
3) Consensus determination
4) Workload management
5) State updating
6) Group unification
Each node periodically executes these algorithms, and thesemodules act independently and communicate with one anotherby means of asynchronous message passing in a coordinatedmanner. The group reorganization algorithm forms a groupfor a service, and then the members of the group share theroles of primary and backup by the (modified version of)
the consensus algorithm. The primary periodically updates
the service states using the state-update algorithm to maintainconsistency among the backups. When a node fails, the failure
detector identifies it and then conveys the information to thegroup reorganization algorithm. In addition, each node haspredetermined upper and lower thresholds, and if the workload
exceeds the upper threshold or falls below the lower threshold,the workload manager detects the condition and conveys thisinformation to the group reogranization algorithm. According
to the messages from the failure detectors and the workload
managers, the group reorganization algorithm periodically
executes the consensus algorithm and changes the membersof the group. Finally, if the existence of multiple primaries is
detected after recovery from a network partitioning, the groupunification algorithm merges the separated groups back into
the original one.
In the following subsections, we briefly overview thesealgorithms.
A. Failure Detection
Failure detectors are popular applications that are responsible for locating node failures or crashes in a distributed
system. Our implementation is based on the usual heartbeatstyle technique. That is, each node periodically transmits its
own heartbeat packet while simultaneously monitoring theheartbeat packets received from other nodes. If a heartbeat
is not observed within a threshold time interval, the receiverconsiders the sender to have failed.
B. Group Reorganization
The group reorganization algorithm manages the formingof a group. This algorithm works in collaboration with theconsensus algorithm, the workload manager, and the groupunification algorithm. Each group is formed so that it satisfies
the following conditions:1) There exists a single primary node.
2) There exist a backups in the same area.
3) There exist b backups in different areas.
4) All backups are placed in at least c different areas.
5) There is no node whose workload exceeds its upper
threshold.
The values of a, b, and c are tunable. If a group cannot
satisfy these conditions because of a node or network failure
or a change in workload, the consensus algorithm sends themessage lack to the group reorganization algorithm. Then thegroup reorganization algorithm sends invite messages to all
the other nodes. A node receiving the invite message replies
with an accept message if it can take over for the missing
node. Finally, the group reorganization algorithm chooses
some of the nodes so as to satisfy these five conditions.
Algorithm 1 Consensus Algorithm
while true do
if p is the coordinator thenreceive messages from the buffer
if receive newgroup(groups ) thengroupps ← groups
end ifif receive f ailure(f ailedN ode) thenf ailedN odep ← f ailedN ode
end ifif receive serviceout(p′ ) thenoutN ode ← outN ode ∪ {p′ }end ifwhile groupx cannot satisfy the group conditions do
send lack to the group reorganization algorithm
wait to receive newgroup(groups ) and groupps ← groups
end while
vprop ← groupps
execute the procedure for consensus
repgroups ← vdecidesend repgroups to the group reorganization algorithm
wait
else
while the coordinator fails do
receive messages from the buffer
if receive newgroup(groups ) thengroupps ← groups
end ifif receive f ailure(f ailedN ode) thenf ailedN odep ← f ailedN ode
end ifif receive serviceout(p′ ) thenoutN ode ← outN ode ∪ {p′ }end ifif receive recP rep or recAccept thensend Ack or N ack
end ifif receive Decide(v) thenrepgroupps ← v
send repgroups to the group reorganization algorithm
end ifend while
end ifend while

C. Consensus Determination
The consensus algorithm is the heart of our approach. Thisalgorithm is used to reach agreement among group members
about which are the primary and the backups, so a decidedupon value determines these assignments.

Our optimistic consensus algorithm behaves as follows: The
coodinator can propose or decide if the number of received
messages reaches a specific value m, which may represent
less than a majority. When a node generates a proposed value,
it checks whether a change in the members is needed. If it
is, the consensus algorithm sends a request to reorganize thegroup. If the group reorganization algorithm finds a possible
reorganization that satisfies the conditions on group members,
the consensus algorithm allocates the roles of the primary andbackups to the new members of the group. After the proposal
is decided, this decided-upon value is sent to the reorganization
algorithm, and then the group is reorganized.
The details are presented in Algorithm 1, where we introduce the following expressions.
• newgroup(groups ): possible members groups ⊆ N for
reorganization of the group of service s• failure(failedNode): a message that the failed nodes are
failedNode ⊆ N• outNode (⊆N ): a list of nodes that need to leave a group• serviceout: a request to leave a group• assign groups : assignment of the primary and the backups.
D. Workload Management
The workload manager monitors the load of its own node.
If this exceeds the upper threshold, the manager sends arequest to the consensus algorithm to release some of its
primaries and backups. In addition, if the workload falls
below the upper threshold, the manager sends a request to
the consensus algorithm to migrate all primaries and backups
to another node. However, if just any request were allowed,
frequent migrations could result. Thus, a request is accepted
if a primary or a backup migrates from a node with a lower
workload to another with a higher load.
E. State Updating
Every primary periodically sends the current state of its
service to all backups, while every backup updates its backup
state with the primary’s message. This procedure is managed
by the state-update algorithm.
F. Group Unification
When a network failure divides a group, our optimistic
consensus, allows two separate groups to be formed andcontinue to provide the same service independently. During
such a network partitioning, the group unification algorithms
periodically send messages to try to communicate with eachother, and if the channel is restored, the algorithms in theseparated groups send a request to the consensus algorithm tounify them into the original group.
VI. E XPERIMENTS WITH I MPLEMENTATION
To verify the correctness of our algorithm and to demonstrate its ability to keep services available, we conducted
experiments with our current prototype implementation of the
proposed method. In addition, to demonstrate the mechanism

TABLE IS ERVER C APACITY AND L OWER AND U PPER T HRESHOLDS#1–#7#8–#14#15–#21#22–#28

Capacity
100
80
100
80

Upper threshold
90
70
90
70

Lower threshold
70
50
70
50

NormalLack of Backups

Lack of PrimaryService 1
Service 2
Service 3
Service 4for load balancing and power saving, we used this implementation to simulate a change in the number of active physicalnodes and the average load in the course of a day in which
the system workload varies.
Our prototype consists mainly of the six modules explainedin the Section V. These modules behave independently andcommunicate with each other by means of asynchronous
message passing. To implement these concurrent processes,
our prototype was implemented in Scala [16]. In particular,
the interprocess communications were implemented by using
Scala Actors library. On the other hand, our implementation
has not reached a practical level: it does not function as an
Internet service platform and cannot execute real application
servers.

Service 50

B. Demonstration of Service Availability
As explained in Section IV, as examples of possible largescale disasters in a real system, we considered the following
two cases:
Case 1. All nodes in area 2 fail.
Case 2. The network between areas 1 and 2 is partitioned.
For each case, there were five services. The primaries forservices 1–3 were placed in area 1, while services 4 and 5
were in area 2. Every service has four backups, which satisfies
the condition described above. The workloads of the primaryand backup were respectively 70 and 20. The results of theexperiments are as follows.
Case 1: All nodes in area 2 fail. Fig. 6 illustrates the
behavior of the system when a failure occurs after a lapseof 50 s. In this experiment, immediately after the failure,

100

150

200

250

300

350

Time (sec)Fig. 6.

Case 1: System behavior when all nodes in an area fail

Normal in Both Areas
Lack of Primary in One Area,
Lack of Backups in One Area

Lack of Primary in One Area,
Lack of Backups in Both Areas
Two Primaries

Service 1
Service 2
Service 3
Service 4
Service 5

A. Experimental Setup
The experiments were conducted on 28 PC servers, eachof which was equipped with 8 Intel Core i7 2.67 GHz CPUs,
11.8 GB memory, and a single 500 GB ATA disk. Each server
was connected to a single switch via a 1000Base-T network
adapter.
We virtually introduced two areas in the system; servers 1–
14 were placed in area 1, while servers 15–28 were in area 2.
As conditions for group membership, each primary must have
two backups in the same area and two in the other, unless therequired nodes are alive. If a group loses some of its backups ina different area and no node remains to take over the backups
in that area, then the group complements them with nodes inthe same area. Instead of installing real software, the server
workloads were simulated by natural numbers. For each server,
the capacity and lower and upper thresholds were set as in
Table I.

50

0

50

100

150

200

250

300

350

Time (sec)Fig. 7.

Case 2: System behavior when network partitioning occurs

services 1–3 lacked backups in area 2, and services 4 and5 lacked both primaries and some of the backups. After 35–
40 s, each of services 1–3 invited two nodes into the groupand complemented the backups. On the other hand, after 57–
76 s, each of services 4 and 5 also complemented the backups,
and one former backup became a primary. We note that forservices 4 and 5, the complementing of the backups andthe election of a primary were accomplished simultaneously.
This is because these procedures are handled by the grouporganization algorithm.
Case 2: The network is partitioned. Fig. 7 illustrates the
behavior of the system when a network failure occurs and how
the system recovers, after lapses of 50 and 250 s, respectively.
During the failure, none of the nodes in different areas cancommunicate with each other. In this experiment, immediately
after the failure, in area 1 services 1–3 lacked backups andservices 4 and 5 lacked both a primary and backups, while
in area 2, services 1–3 lacked both a primary and backups
and services 4 and 5 lacked backups. After 40 s, services 1–3
in area 1, as well as services 4 and 5 in area 2, obtained therequired number of backups. Then, after 12 s, all primaries andbackups were complemented. Furthermore, after 250–300 s,
for each service the multiple primaries merged into a single
one.
From the results of these experiments, we conclude that
our mechanism behaves as intended and makes it possible tocontinue to provide services in environments where more thanhalf the total number of nodes fail or network communication

Average(Max/Min) Load of the System

200

150

100

50

0
0

4

8

12

16

20

24

Time (hour)Fig. 8.

Average (max/min) system load

The Number of Active Nodes

30
25
20
15

which is intercloud environments. The key idea is to use an
optimistic consensus algorithm that allows agreement to bereached with fewer than half of the of nodes participating,as opposed to a traditional majority-based one. In addition,
through interservice communications, members of service
groups are autonomously reorganized according to the typeof failure and changes in system load. This enables both loadbalancing and power saving, as well as provisioning for the
next failure. Experiments show that our mechanism indeed
behaves in the intended manner and can tolerate various failure
patterns, including a simultaneous failure of the majority
of nodes or a partitioning of the network. Moreover, ourmechanism effectively skews workload, thereby reducing therunning time of active nodes.
In future work, we will investigate further to refine our prototype implementation. In particular, we intend to implement
functions to provide real services on the system for practicaluse.
R EFERENCES

10
5
0
0

4

8

12

16

20

24

Time (hour)Fig. 9.

Number of active nodes

between different areas is lost.
C. Demonstration of Load Balancing and Power Reduction
In this experiment, we introduced 10 services. Five primaries are initially located in each area. In the intended
environment, we considered the system load to vary overthe day. During the course of a day, the workloads of every
primary and backup were initially 30 and 10, respectively, andthese were incremented by values of 2 and 1 every 36 minutes
until the middle of the day (when the workloads were 70 and30) and then decreased until the end, respectively. We assumed
that a node storing no primary or backups was at low power;
otherwise it was active.
Figs. 8 and 9 illustrate the change in the average (as wellas maximum and minimum) workload of active nodes and thenumber of active nodes. Fig. 8 shows that the average load
was in the range of 60%–80%, which is about the same as therange of predetermined upper and lower thresholds. However,
because of the limitation of allocating backups, our mechanism
could not achieve an optimal configuration. Fig. 9 showsthat our mechanism adjusts the number of physical nodes
to the variation in workload and reduces power consumption
effectively. Indeed, if we consider a static configuration (i.e.,
without migration), it is necessary to activate 20 nodes to deal
with the system load in this setting.
VII. C ONCLUSIONS AND F UTURE W ORK
We have proposed an optimistic primary-backup mechanism
for highly available Internet services, the prime application of[1] E. A. Brewer. Towards robust distributed systems (Invited Talk). Principles of Distributed Computing (PODC 2000), 2000.
[2] T. Bostoen and S. Mullender. Power-Reduction Techniques for DataCenter Storage Systems. ACM Computing Surveys, vol.45(3), 2013.
[3] N. Budhiraja, K. Marzullo, F. B. Schneider, and S. Toueg. The primarybackup approach. Distributed Systems (2nd ed.), ACM press/AddisonWesley Publishing Co., pp.199-216, 1993.
[4] G. Coulouris, J. Dollimore, and T. Kindberg. Chapter 12 in Distributed
Systems: Concepts and Design (4th Edition), Addison Wesley, 2005.
[5] B. Cully, G. Lefebvre, D. Meyer, M. Feeley, N. Hutchinson, and A.
Warfield. Remus: High Availability via Asynchronous Virtual Machine
Replication. USENIX NSDI’08, pp.161-174, 2008.
[6] X. Defago and A. Schiper. Semi-Passive Replication and Lazy Consensus.
Journal of Parallel and Distributed Systems, vol.64(12), pp.1380-1398,
2004.
[7] E. W. Dijkstra. Self-Stabilizing System in Spite of Distributed Control.
Communication of the ACM, vol.17(11), pp.643-644, 1974.
[8] S. Dolev. Self-Stabilization. MIT Press, 2000.
[9] S. Dolev, R. I. Kat, and E. M. Schiller. When Consensus Meets SelfStabilization. Journal of Computer and System Science, vol.76(8), pp.884900, 2010.
[10] S. Gilbert and N. Lynch. Brewer’s Conjecture and the Feasibility ofConsistent, Available, Partition-Tolerant Web Services. ACM SIGACT
News, vol.33(2), pp.51-59, 2002.
[11] R. Guerraoui and A. Schiper. Consensus Service: a modular approach forbuilding agreement protocols in distributed system. Annual Symposium on
Fault Tolerant Computing, pp.168-177, 1996.
[12] K. Hasebe, T. Niwa, A. Sugiki, and K. Kato. Power-Saving in LargeScale Storage Systems with Data Migration. 2nd IEEE International
Conference on Cloud Computing Technology and Science (CloudCom
2010), pp. 266-273, 2010.
[13] K. Hasebe, K. Yamatozaki, A. Sugiki, and K. Kato. Self-Stabilizing
Passive Replication for Internet Service Platforms. 4th IFIP International
Conference on New Technologies, Mobility and Security (NTMS 2011), 6
pages, 2011.
[14] L. Lamport. The Part-time Parliament. ACM TOCS, vol.16(2), pp.133169, 1998.
[15] D. Mazieres. Paxos Made Practical. Technical report, 2007 (available at
http://www.scs.stanford.edu/ dm/home/papers/).
[16] M. Odersky, L. Spoon, and B. Venners. Programming in Scala, Artima,
2008.
[17] F. B. Schneider. Implementing Fault-Tolerant Services Using the State
Machine Approach: A Tutorial. ACM Computing Surveys, vol.22(4),pp.299-319, 1990.
[18] D. Stodden. Semi-Active Workload Replication and Live Migration with
Paravirtual Machines. Xen Summit, 2007.