6.826 Principles of Computer SystemsSample ProjectsMarch 11, 20001 Air-Traffic ControlIn an alternate universe, computer technology developed much faster than aviation technology. As you werewalking down Vassar street late one night, a physics experiment in an adjacent building created a time-spacesingularity that transported you into this alternate universe. When you get there, you are surprised to learnthat airplanes are considered to be an extremely dangerous form of travel, because the planes are alwayscrashing into each other on the runways when they take off and land.You decide to support yourself by building an air-traffic control system that manages the arrivals anddepartures of airplanes to minimize the crashes. You sell the the Grand Poo-Bah of the country on the ideaby promising that there will be no more crashes. Now you have to deliver on your promise (or more precisely,keep convincing the Grand Poo-Bah that a working system is just around the corner if he keeps giving youmore money).Luckily, you took 6.826 the semester before your fateful trip down Vassar street, so you know to do adesign of the system in Spec before you start to hack. You should first develop a Spec that says what thesystem should do. Your system will control an individual airport. Planes will come into the system in oneof two ways:1. They request a take off slot to leave the airport.2. They come into in your controlled airspace and request a landing slot to arrive at the airport.Airplanes typically take one of several standard routes into and out of the airport, and you need to besure that there are no collisions on the runways or on the routes in the airspace surrounding the airport.You will probably need to model the runways, the airspace, the arrival of the airplanes into the system,and the departure of airplanes from the system. You then develop an implementation that schedules thearrivals and departures. You can make some reasonable assumptions about the arrival rates as long as theseassumptions are made explicit. You should strive to let planes take off as soon as possible after they enterthe system to depart the airport, and let planes land as soon as possible after they enter the system to landat an airport. Also be sure that airplanes can land before they run out of fuel.2 White Pages Lookup SystemYou have recently acquired a tape of all the telephone directories in the United States. The data in this tapewas acquired by obtaining a White Pages telephone book from each region in the United States, then hiringcheap labor to type each book into a database.You decide to start a company to make this data available on the Internet. The spec for your system issimple: given a name, find the number. Or, given a number, find the name. Maybe you even want to delivermore value and let people search by name and state, city, zip code or county. Unfortunately, the data is toobig to fit into the main memory of your machine, and is even too big to fit into a single disk. You realizeyou’ll have to have at least 5 disks just to hold the raw data. And you can’t just stop there. To access the1data fast enough, you’ll have to build indexes, and maybe even store the indexes on extra disks. If you arereally ambitious you’ll figure out how to keep the data available even if one of your disks fails.Your job is to figure out how to architect the system. You’ll have to make reasonable assumptions aboutthe data set size and distribution, then come up with an implementation that works for those assumptions.3 Flood Management SystemThe goal of this project is to specify and implement a flood management system. The system consists of aset of rivers, dams, and water level sensors. When it rains upstream, the water flows into the river and thewater level rises. The water then flows downstream, raising the water level as it does so. The system shouldensure that the water level at each dam never rises above the height of the dam. If it does, the dam will fail,catastrophically flooding the towns downstream.Each dam has a spillway that can be opened to let more water out of the lake behind the dam in acontrolled way. When it rains and the water level rises upstream, your system must anticipate how muchwater will flow into the lake behind the dam and preemptively open the spillway to ensure that there isenough room in the lake to hold the excess water. One way to do this is to always keep the spillwaycompletely open. But of course this negates the purpose of the dams, which is to build up waterskiing lakesfor wealthy suburbanites. So your system should also have a target water level for each dam and attemptto keep the lake at that level whenever possible.You will have to model the river basin and come up with a specification that captures the requirementsof this system. We are not expecting you to do any complicated differential equations or continuous math-ematics; you can use a very simple model that discretizes the system at the granularity of, say, hours. Youcan also make some reasonable assumptions about the maximum possible change in water levels that cantake place over the space of an hour. You will then develop an implementation that decides when to openeach spillway to ensure the absence of catastrophic floods.4 E-commerceYou are designing a modern business-to-consumer e-commerce system, similar to amazon.com. The basicfunction of the system is to sell books. To do this, it needs a catalog of available books, a way for the userto search the catalog and order books, a shopping basket that records the user’s current order, a way for theuser to provide credit card and shipping information and be charged for the order, and a way to ship theorder.There are many extensions: remembering the user’s information from one day to the next, keeping trackof past and pending orders, handling returns, handling disputed charges, keeping track of inventory andordering from your distributors, aggregating orders from lots of users and recommending related books basedon this information, posting sales ranks, recording book reviews from staff or users, one-click ordering, andexpanding to other types of merchandise. There are also implementation issues: scalability and availability.Some of these are essential for your site to stay in business, others may be important to grow your business.The external interfaces of this system are the web pages displayed to the user, the credit card system,and the wholesale distributors