Homework 6: Due in class on Thursday, November 2

Because of the project, this is the last non-project homework assignment you’ll receive in CS514. Solutions to this problem should be about a page of typed material – certainly not more. If you can give a complete answer in less than a page, this will be fine with Professor Birman!

Non-determinism. When solving homework 4 (the Nasa assignment), quite a few people proposed mechanisms that only work for programs that are deterministic.

a) List all the sources of non-determinism that arise in the programming language and operating system with which you are most familiar. For a lot of people, this will probably be C or C++ under Unix, or Java on an NT platform. I’m looking for an answer that focuses on possible non-determinism in a single application that you might code, but one coded using all the different mechanisms that this language and runtime environment provide. So, even if you are not in the habit of using such and such a Unix mechanism, if using it could result in a non-deterministic behavior, I would like to see the mechanism on your list. For each item, give a one-line explanation of how it can introduce non-determinism. Keep in mind that in modern component-oriented systems, what is logically “one program” might be implemented using shared libraries and multiple components, and might even have a client-server structure. For simplicity, you can assume that we aren’t talking about a network here – the program runs on a single machine, although it might be implemented using more than one process.

b) For this same setting, explain what would need to be done to write a deterministic program. Now, keep in mind that we use pre-built libraries and system call libraries all the time. Presumably, these might or might not respect your list of “rules and regulations” for running deterministically. Is it possible to at least “detect” when a program does something non-deterministic so that an exception can be thrown? Or will programmers who want to write deterministic code need to write their own procedures for everything, including rewriting system-call libraries and the like?

c) Revisit the Nasa application from homework 4. How likely is it that Nasa could live with the rules you proposed in part b?