Final Project: Distributed Transaction System

Can work in groups of up to 4 people. (I really wanted only three but since you have already formed groups of 2, forming into groups of 4 is probably easier than 3.)

Internet services have become essential to lots of people. And one of the services people use frequently is on-line flight reservation. These systems must be reliable and highly available, so that clients can trust it and actually use it.

Your job is to write a simplified distributed and reliable flight reservation service for the internet. You should run at least 3 servers on three independent machines you choose (the more machines you use, the better your work will be). Servers are to accept several types of requests from potentially multiple clients simultaneously. Feel free to extend or modify the list below:

• Query route: Parameter <from, to>, return <flight #>. Checks whether there are flights between cities from and to. Returns flight number, if such a flight exists.
• Reserve seat: Parameter <flight #, type>, returns <seat #>. Reserves a seat of type type on flight flight #. The reserved seat cannot be reserved again.
• Cancel seat reservation: Parameter <flight #, seat #>. Cancels a previous reservation for a seat on a flight.
• Specify meal restriction: Parameter <flight #, seat #, meal type>. Determines the type of meal to be served to passenger.

Note that the databased maintained by the service must be partitioned across the servers. That is, you cannot assume that the servers have access to the same remotely mounted file system.

Clients and servers must use the TCP protocol for communication. (You can re-use infrastructure you generated for previous assignments.) A client should choose a server randomly and stick with it for the duration of a "session" (ie, until the client finilizes all his/hers transactions). Multiple clients may be accessing the same flights. Servers should maintain just enough state as to complete the transactions. For locking, you should use the two-phase locking algorithm. For atomicity, you should use the two-phase commit protocol.

In more detail, a client is simply a program that will read in a text file or user's input (feel free to specify your own format - you may find that a menu driven interface will be easier to implement than a parser for this file) such as:

flight1 = QUERY_ROUTE New York, Los Angeles
flight2 = QUERY_ROUTE Los Angeles, Tokyo
BEGIN-TRANSACTION
seat1 = RESERVE_SEAT flight1, WINDOW
SPECIFY_MEAL_TYPE flight1, seat1, VEGGIE
seat2 = RESERVE_SEAT flight2, CENTER
SPECIFY_MEAL_TYPE flight2, seat2, BEEF
END-TRANSACTION

The servers will have to use two-phase locking (to lock each of the flights in the example above) and two-phase commit to guarantee the atomicity of the transaction. Each server should also keep (on disk) a log of the operations it performs to help with atomicity. All operations to be executed should be written to the log (and flushed to disk). In case of a server crash, upon recovery the log has to be read starting from its end back to the last commit point and any operations described in the log should be undone.

This is a hard assignment, so start early and do your best. Good luck.

What you should submit:

• A report containing the description of what you did. Your report should contain your names, e-mails and student ID numbers. Your report should explain (in enough details for me to understand) what you've done, how you implemented and how you tested your work. There is no need to write long introductions to the topic nor to motivate the assignment. Write down all the difficulties you had, all challenges you've found and what you could not implement and why.
• Your test results must show concurrent updates to the same flights and a proof that the updates happened with mutual exclusion. Also, you should prove that your transactions (involve multiple operations with multiple flights) either happened successfully or didn't happen at all, especially if one of the servers crashes (you should simulate a failure). All servers must have a unique view of the system and must agree on the seat allocations at all times.
• The source code (without object files - the .o files - and without the executables) for everything you've done, including all test files you used and scripts and results. The more you comment the source files, the easiest it will be for me to assign you a grade.
• A brief README file describing all the modules (.c files) of your source code. The README file should also contain description of how to use, compile (flags needed, libraries used) and test your code. Your README should also include discussions you may find useful. Write your problems, challenges and anything else that you think will help me grade it. You may include a Postscript file or a PDF file as a report in your electronic submission but make sure you mention in the README file you're including this report in another format.