Consider a set of players who wish to randomly arrange themselves without a trusted third-party. For example, if there are 3 players, a, b and c, then a trusted third party could order them as abc, acb, bac, bca, cab, or cba. In the absence of a trusted third party, the players want to select one of these permutations for themselves at random. In this writing, a protocol (named RandomSelect) is presented using multiplayer computation. From a bag of all possible ways the players could be ordered, RandomSelect provides a means for players to make local choices that when combined, jointly select a permutation randomly. The RandomSelect protocol supports any number (n) of two or more players and computes properly even if n-1 players collude. Communication is O(n) using a broadcast channel. More generally, necessary and sufficient conditions for a class of functions called RandomOrder functions are defined. A RandomOrder function uses n inputs to make a random selection of a string from a bag of n! strings where all possible selections are uniformly distributed over the possible inputs and over the strings. Any RandomOrder function can be used in the RandomSelect protocol. Bio-terrorism surveillance is used as an example application.

41 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu