Simulating Stochastic Models

Recently I’ve been tasked with working on an infrastructure system which comprises several computationally intensive tasks that can be scheduled on a series of host machines. Some tasks have dependencies on other tasks, and cannot be scheduled before its dependencies have finished. In a simplified setup we assume that any task can run on any machine, provided that machine is not busy with running another task.

The following picture illustrates the system

Host A runs task 1 and 3, while host B runs task 2 and 4. Task 4 has a dependency on task 1 and task 3 has one on task 2. When all tasks are completed the job is considered completed. It is evident from the picture that a task (task 3) may be delayed in its scheduling even though its dependencies are satisfied due to resource constraints.

Solving ‘The Monty Hall Problem’ using Models

Today is about my favorite probability puzzle – The Monty Hall problem. If you haven’t heard of it before you are in for a treat. The problem stated goes as follows (from Wikipedia):

Suppose you're on a game show, and you're given the choice of three doors: Behind one door is a car; behind the others, goats*. You pick a door, say No. 1 [but the door is not opened], and the host, who knows what's behind the doors, opens another door, say No. 3, which has a goat**. He then says to you, "Do you want to pick door No. 2?" Is it to your advantage to switch your choice?

Vos Savant's response was that the contestant should always switch to the other door. […]

Many readers refused to believe that switching is beneficial. After the Monty Hall problem appeared in Parade, approximately 10,000 readers, including nearly 1,000 with PhDs, wrote to the magazine claiming that vos Savant was wrong. (Tierney 1991) Even when given explanations, simulations, and formal mathematical proofs, many people still do not accept that switching is the best strategy.

*The probability of the car being behind any door is uniformly 1/3

**The door that is opened has to have a goat behind it, and it cannot be the one you picked initially, in case the host has multiple choices it is assumed that s/he chooses uniformly at random

The problem is brilliant in its simplicity and the correct answer feels extremely counter-intuitive at first. The natural tendency is to think that it makes no difference whether you switch or not – but the truth is that you should switch! And hopefully once you are done reading this article you will be convinced why.

Can your tests stand the ‘test of time’?

Today I want to digress a bit from Model-Based Testing and talk about a general issue in software testing, applicable to all types of testing. My focus will be on the use of time-dependent methods in test code. These include library functions like ‘DateTime.Now’, reading the BIOS clock, retrieving the current time from a time server, etc. The use of time dependent methods can lead to unpredictable behavior and is a common source for fragility in tests.

But first, let’s look at a definition of time. From Wikipedia:

Time is the indefinite continued progress of existence and events that occur in apparently irreversible succession from the past through the present to the future.

There are two vital pieces of information in this definition. They are continued progress and irreversible. There is nothing about size and quantity of time in the definition. In fact our daily representation of time in hours, minutes, seconds, milliseconds, etc. is completely arbitrary. Instead I like to think of time in a mathematical sense, as a strictly increasing series t : t_i < t_i+1. The absolute value of t_i is irrelevant.

This is how I believe time should be view in test code, in fact I will postulate a “test of time” at the end of this article.

I will assume that we all agree fragile tests are costly to maintain, and have no place in a regressions suite.

Common misuses of time #1: Validation of time-dependent data

Common misuses of time is validation of messages, dialogs, errors and other strings containing the current time generated by the system under test. I recently saw a test case validating a text containing the latest updated time of a graph. The test would look something like:

            graph.Update();

            String expectedMessage = String.Format("Last update: {0}", DateTime.Now.TimeOfDay.ToString(@"hh\:mm"));

            Assert.AreEqual(graph.StatusMessage, expectedMessage, "Incorrect status message displayed");