Computer Science

Graduate Research Forum Details

Using N-Trees for Scalable Event Ordering in Peer-to-Peer Games

Abstract

Event ordering is a fundamental problem that must be solved to fully realize large-scale multi-player peer-to-peer games. Even without faults, event ordering requires all-to-all message passing with at least two rounds of communication [12]. Multiplayer games add real-time constraints to this scenario. To meet this challenge, we have developed an event scoping mechanism that uses N-Trees for event propagation. Unlike traditional application-layer multicast, N-Trees organize peers by their application-level scope of interest, instead of by their delay-based shortest-path tree. This organization allows peers which are close by in the virtual world to order events without needing to communicate with other peers that are farther away. We show the asymptotic analysis of N-Trees indicates that they will perform well for scalable peer-to-peer event ordering. We also provide an analysis of N-Trees in comparison to other distributed architectures for peer-to-peer games and show some initial simulation results.