Phase IV: Availability Through Active Replication or Primary-Backup Replication

Due: 9:00am Tuesday April 26.

Background: Making Bank Branches Available

In the distributed banking system built for Phase III, bank accounts (and the funds they store) at crashed branches are unavailable until the faulty host has been repaired and restarted. Few bank customers would be willing to tolerate such outages often, if at all. More generally, the increasing dependence by business on computers for daily operations means that high-availability is no longer a requirement only for life-critical control settings. Implementing availability in our banking systems is thus not an atypical concern.

For Phase IV we want you to pick one of two methods for replicating a branch server to make it highly available. One is easier to implement and the other is more general and powerful. You must decide which approach to take and then once you make this decision, will need to deliver on the concept.

Option A (simpler): Primary/Backup Replication

For this scheme, we would like you to extend your solution to Phase III by adding a “warm standby”. This is a branch server that is running in the background (normally on a different machine, but for our purposes we won’t insist on that), reading data from the primary server to track its state and hence ready to jump in if the primary server fails.

What to Build

For this option, you should be able to simply extend your Phase III solution. Two major issues arise:

• We would like the backup server to be a warm standby. As noted above, this means it runs continuously and is always ready to step in and take over from the primary.
• Making life a bit more complex, as usual we expect that communication be through our UDP layer, which is unreliable and can deliver messages out of order. You may assume a branch primary and its backup can always talk directly. However, you can’t use TCP for these channels. Accordingly, you’ll need to implement a failure detection mechanism. We recommend that it take the form of a “dead man switch.” This means that the primary must periodically send some sort of a “still fine” message to the backup and if it fails to do so a few times in a row, the backup assumes the primary has failed and takes over. The solution does not need to handle “mistaken” fault detection.

Option B (harder): Process Group Replication

Process group replication is one way that an application can be made highly available. Services and data are replicated; requests are processed by enough replicas so that processor failures can be masked. In this phase of the cs514 project, you will program such active replication. This will give you an opportunity to master and get hands-on experience with the state machine approach.

What to Build

For this phase, it will be helpful to design code that can assume:

• Processor failures are benign (i.e. failstop) and not Byzantine.
• No branch GUI ever fails.
• Each communication channel is bidirectional.
• Communication channels are reliable and FIFO.
• Every bank branch is directly connected to every other. Thus, higher layers of software see a network topology that looks like a completely connected graph (i.e., with N*(N-1) bi-directional edges

As in our previous phases, the raw communication primitive available to you is UDP. Since UDP lacks the properties just lised, you should implement a communications layer that provides this functionality over the UDP layer, or reuse the layer you developed for Phases II or III. Warning: Most groups will need to modify their routing functionality from earlier phases for use in option B of phase IV.

Tools to use. Hackers may want to just roll-their-own solution using protocols that we developed in class… but this is hard. Other possibilities include downloading the JGroups toolkit from www.jgroups.org, or Spread from www.spreadsystems.com, or Ensemble from www.Cornell.edu (support is moving to Hebrew University so Ensemble users should check for new versions from them starting in mid 2005). These technologies offer a mixture of properties and can be used from various languages. Only Ensemble has actual support for .NET and Visual C# (or at least it did last time we looked).

Simulating Failstop Failures. Extend the branch GUI from Phase I with a "button" that instigates the failure of the branch server. Activating this button should cause behavior that simulates the failstop failure for the branch server, as follows.

1. Send a message to each of neighbor, announcing that this branch server has failed.
2. Abruptly terminate the branch server application and any other software written for this phase that is running on the failed host. (Do not cause the branch GUI to terminate, because the branch GUI will serve to simulate the control panel for the host at that branch.)
3. After some time has passed (say 30 seconds) since the branch server has terminated, cause a new copy of the branch server to start and run some "recovery code".

Replication Protocols. A branch server can be replicated by running a copy of it on other hosts in the banking system. There are two ways to orchestrate running a replica of branch server for branch B1 (say) on the host for branch B2 (say):

1. Modify the branch server at branch B2. The modified branch server not only processes the operations (commands) that it used to (e.g. Deposit, Withdraw, Query, Transfer for that branch's accounts) but this modified branch server also handles these operations for branch B1. Effectively, we are merging new branch server replicas with the branch server that already exists at each host.
2. Instantiate at branch B2 a copy of the branch server for branch B1, and associate this copy with a new socket at the host running branch server B2. Note that you may have to modify your "network wrapper class" to accommodate any additional sockets now in use.

As far as the state machine approach is concerned, each branch GUI should be viewed as a client. This means that the branch GUI (and possibly the branch servers) will now be receiving multiple responses for each operation it initiates and, therefore, it must convert those responses into a single one (which is then presented to the human user). Because the mechanism for combining responses resides in the branch GUI, it never experiences failures.

The replication approach is mostly concerned with orchestrating the delivery of client commands to various replicas, using abcast.  You can implement a solution in the "static" membership model, or go for a "dynamic membership" solution if you prefer.  In the former model a quorum scheme will work best. Since we assume that failures are fail-stop, the choice of protocol that you implement should reflect that. For additional credit, feel free to

• add periodic broadcasts by various system components in order to speed-up request processing, and/or
• employ assumptions about message delivery delays and clock synchrony in order to speed-up request processing.

Note that both of these additional-credit options require programming as well as making design decisions. What components should issue additional broadcasts and how often? What assumptions about message delivery delays and clock synchrony are reasonable for the actual hardware and software you are working with? The amount of credit you receive will be based not only on your answers to these questions but also on your discussion of how you obtained those answers.

The best solutions will be ones that do NOT download and use pre-existing implementations of reliable group communication, such as the ones in Ensemble or Spread.  We prefer that you build a solution of your own.  As noted, a quorum-based mechanism will be easiest and will gain full credit. But we also understand that we’re asking a lot of you here. If you do download a package and use it, you’ll get full credit if the resulting system is “feature rich” and shows a level of effort that makes up for the short-cut of not doing all these protocols on your own!

Your simulation of a failstop failure has a branch server restart and run "recovery code" 30 seconds after a failure. For this phase, the "recovery code" should do nothing; in the next phase, you will develop recovery protocols.

Configuration Management. The fault-tolerance of a replicated "state machine" is defined by the degree of replication. There are actually two design questions:

1. How many replicas of each state machine to run.
2. Which hosts should run these replicas (assuming that there are fewer replicas than hosts).

For answers, your implementation should read from a new file, called CONFIG. This file should state how many replicas to create for each branch server replica and which hosts will run those replicas. You may assume that CONFIG is readable by all branch servers.

Submission Procedure. The usual, plus:

README which contains

· The names and a description of the contents for the other files in the directory.

· Instructions for installing, compiling, and running your software on our system.

· A tutorial that the grader can follow to start your software and to convince himself that your system implements the required functionality. Expect the grader to spend at most 10 minutes on this task.

LOGIC which contains a brief description of the specific protocols that were implemented. Include an analysis of how many and what kinds of failures your distributed banking system can tolerate. Do you make assumptions whose violations constitute failures of system components?

CONFIG which contains a description of the numbers and locations of state machine replicas.

Grading. Your grade will be based on the following elements:

• Does your system correctly implement active replication with the state machine approach?
• How easy is it to follow the README file installation and sample-execution script?
• Is the source code easy to understand and does it exhibit good structure?