CS 414 Fall 2001: Homework 3 (due Oct 25)

Please type your solutions.

In solving the following two problems, assume that every computer on the network has a unique IP address and that communication between application programs is by unreliable point-to-point messages of arbitrary size (in effect, via UDP). As described below, programs can fail by crashing – halting – but not in other ways. For example, programs never go haywire and start to send corrupted messages with garbled content. Similarly, assume that the network can lose messages, deliver them out of order, and can even deliver more than one copy of the same message, but that it never damages a message. Finally, assume that there are no permanent network outages. Communication between process A and process B can be disrupted for an extended period of time, but not forever – if A hasn’t crashed and B hasn’t crashed, sooner or later some messages will get through provided that you send them again and again. But nobody knows the “time bound” on outages – a network outage could last for just a fraction of a second, but it could also last for minutes or hours.

1. Suppose that you are designing software for a new kind of computing system that will run on the Internet and will assist in automating patient care for a hospital. The idea is that patients will wear small units that can automatically administer drugs, and the hospital computing system, using protocols that run over the computer network, will adjust the dosages based on telemetry data from the patient and orders given by the doctor. Everything will be encrypted so that even though the data passes over the Internet, intruders can’t make sense of these packets or modify them in any way.

a) Any device can fail – these little devices, for example, depend on a battery pack and the battery can run low. Suppose that the device never fails midway through giving an injection, and that it fails by halting – crashing. Can a protocol be designed so that if the doctor says “inject x units of drug y” either the doctor is told within a few seconds that “the device failed and the injection wasn’t administered”, or the injection is performed exactly once and within a few seconds, the doctor is told “successful”? E.g. there should never be an “outcome uncertain” situation. Explain briefly, and if you believe the problem can be solved, give the protocol – “First, the application on the doctor’s desktop sends a message to the device containing…,” etc. Give us a short proof for the correctness of your algorithm. If you are convinced the problem can’t be solved, give a short proof that it can’t be solved.

b) What sorts of non-technical (human) roles need to be included in the kind of hospital system we’re talking about? Keep in mind that on the one hand, the hospital must keep expenses to a minimum. On the other hand, the hospital also must keep patients safe. Your answer should be reasonably brief – a paragraph or two, not pages. Base your answer on technical observations about the feasibility or infeasibility of solving technical problems (like in a), but try and translate those observations to conclusions about how to run the system safely.

2. Suppose that you have a set of 3 email servers {s₀, s₁, s₂} and want to send an email in a manner that is guaranteed to get through reliably provided that no more than 1 server is ever down at any point in time. You can assume that a recovering server is solidly up again before any other failure occurs. Thus when an email is sent there may be 2 servers running or all 3 may be running. There would never be less than 2 servers running. Describe a protocol for sending a mail message, a protocol for checking for mail, and a protocol for deleting a mail message which will work correctly as long as these assumptions are satisfied. In designing your protocol you can add additional information to a mail message if necessary, such as the IP address of the sending machine, counters, the time, etc. But tell us what this extra information is, and use a Java-like notation for any code that you actually write down.