Case Studies—Complete Time

The appropriate value for complete time depends upon the goals of the program, and on its operating environment. These case studies illustrate the criteria for selecting the value for this parameter.

Mandelbrot Set

Because it generates beautiful displays, the Mandelbrot set is a popular visual symbol of fractal phenomena. Consider an example application that computes a Mandelbrot display, using a distributed queue of servers to compute the display data.

A display component divides the display region into small chunks (tasks), and sends each chunk to the server group for concurrent processing. Within the group, the scheduler assigns each chunk to an available worker. The worker computes the data for its chunk, and sends the results to the display component, which reassembles and displays them.

Mandelbrot computations are characterized by many small chunks of processing, each of which completes in a short time—estimate under 0.1 seconds. Estimate the network travel time for each task at a few milliseconds. Duplicate processing does no harm (other than wasted effort). The main priority is fast response, since the user is waiting for the display.

For programs with these criteria, consider a complete time of 0.5 seconds. Any task that is still incomplete after 0.5 seconds is reassigned, so the display user perceives only minimal delay, even in exceptional situations. Yet 0.5 seconds is sufficiently high to prevent thrashing in the event of several slow workers; use empirical data to fine tune this parameter.

Fax Confirmation

Consider a business that relies on telephone transactions between customers and service representatives. At the conclusion of each call, the customer receives a one-page summary and confirmation by fax.

A large number of service representatives all send certified tasks to a distributed queue of fax servers. When a fax server receives a task, it transmits the fax and notes the result in the customer’s database record.

Each fax task could take several minutes—including redials and other delays. Estimate the network travel time for each task at a few milliseconds. Speed is not critical; the customer is satisfied as long as the fax arrives within 10 minutes. The highest priority is that each task completes (that is, no task is lost). However, duplicated tasks are undesirable—customers prefer to receive only one fax summary.

For programs with these criteria, consider a complete time of 300 seconds (5 minutes). If a task remains incomplete for 5 minutes, the scheduler reassigns the task to another server.