Categories
Publications

Parallel Randomness

dice

My latest paper Evaluation of splittable pseudo-random generators has appeared online last week in the Journal of Functional Programming.

What is the big deal of randomness? Randomness is the key to several common applications of computers, including games and secure communication to name but two of the most obvious ones. Games, such as lotteries and poker, are obviously supposed to be random. Imperfect randomness amounts to loading the dice. Secure communications may be less obvious to the uninitated, but the cryptography which is used to keep secrets depends on random keys to be secure. Loaded dice gives the attacker or intruder an edge. And obviously we want our banking and credit card transactions to be secure.

Programming randomness in computers was recognised as an importent challenge even in the early days of computing (around 1950), and it has been studied ever since. One would think the topic be exhausted by now. In fact, I believed enough had been written on computer randomness when I started this work in 2013.

In fact, randomness is well understood for application in sequential computer programs, i.e. a program which only utilises one of the CPU cores in the computer. A typical consumer-end computer these days has four. If you want to use all of them in one application, the software must be written for parallel execution.

True randomness is hard to achieve in a computer. It is possible to a certain degree, but a large number of random values take time to generate. Instead, the common solution is a so-called pseudo-random number generator (PRNG). Many exist. Most of them are flawed, but there are enough PRNG constructions which are considered trustworthy. However, the well-known solutions are all sequential. The random numbers are generated one by one in sequence. Distributing randomness across parallel threads (or multiple cores in the CPU to take a concrete view) is non-trivial.

Parallel randomness was recognised as an important problem already in the first half of the 1980-s. Yet, the literature is sparse. Some constructions have appeared, but few inspires any confidence. In fact, my paper demonstrates serious flaws in almost all of the known constructions. The first solution which inspires any confidence is that of Claessen and Pałka in 2013.

A preprint is available on my web page.

My name is Robin T. Bye and I am an associate professor in automation engineering at NTNU in Ålesund, Norway. In addition to teaching and supervision, I am the head of the Cyber-Physical Systems Lab. My research interests belong to the broad areas of cybernetics, artificial intelligence, neuroengineering, and education.

By robintb

My name is Robin T. Bye and I am an associate professor in automation engineering at NTNU in Ålesund, Norway. In addition to teaching and supervision, I am the head of the Cyber-Physical Systems Lab. My research interests belong to the broad areas of cybernetics, artificial intelligence, neuroengineering, and education.

Leave a Reply

Your email address will not be published. Required fields are marked *