Probabilistic Event Resolution with the Pairwise Random Protocol

John L. Miller and Jon Crowcroft

Abstract

Peer-to-peer distributed virtual environments (DVE's) distribute state tracking and state transitions. Many DVE's - such as online games - require ways to fairly determine the outcome of probabilistic events. While trivial when a trusted third party is involved, resolving these actions fairly between adversaries without a trusted third party is much more difficult. This paper proposes the Pairwise Random Protocol (PRP), which uses secure coin flipping to enable adversaries to fairly determine the result of a probabilistic event without a trusted third party. Three different variations of PRP are presented, and the time impact and network overhead are examined. We conclude that PRP enables DVE’s to distribute the work of determining probabilistic events between adversaries without loss of security or fairness, and with acceptable overhead.

Details

Publication typeInproceedings
Published inNOSSDAV '09: Proceedings of the 19th International Workshop on Network and Operating Systems Support for Digital Audio and Video
PublisherAssociation for Computing Machinery, Inc.
> Publications > Probabilistic Event Resolution with the Pairwise Random Protocol