Journal of Functional Programming

Articles

Distributed random number generation*

F. Warren Burtona1 and Rex L. Pagea2

a1 School of Computing Science, Simon Fraser University, Burnaby, British Columbia, Canada V5A 1S6 burton@cs.sfu.ca

a2 Amoco Production Company, Research Center, 4502 East 41st Street, Post Office Box 3385, Tulsa, Oklahoma 74102, USA rpage@trc.amoco.com

Abstract

In a functional program, a simple random number generator may generate a lazy list of random numbers. This is fine when the random numbers are consumed sequentially at a single point in the program. However, things are more complicated in a program where random numbers are used at many locations, such as in a large simulation. The programmer should not need to worry about providing separate generators with a unique seed at each point where random numbers are used. At the same time, the programmer should not need to coordinate the use of a single stream of random numbers in many parts of the program, which can be particularly difficult with lazy evaluation or parallel processing.

We discuss several techniques for distributing random numbers to various parts of a program, and some methods of allowing different program components to evaluate random numbers locally. We then propose a new approach in which a random number sequence can be split at a random point to produce a pair of random number sequences that can be used independently at different points in the computation.

The approach can also be used in distributed procedural programs, where it is desirable to avoid dealing with a single source of random numbers. The approach has the added advantage of producing repeatable results, as might be needed in debugging, for example.