We explore exploits possible for cheating in real-time, multiplayer games for both client-server and distributed, serverless architectures. We offer the first formalization of cheating in online games and propose an initial set of strong solutions. We propose a protocol that has provable anti-cheating guarantees, but suffers a performance penalty. We then develop an extended version of this protocol, called asynchronous synchronization, which avoids the penalty, is serverless, offers provable anti-cheating guarantees, is robust in the face of packet loss, and provides for significantly increased communication performance. This technique is applicable to common game features as well as clustering and cell-based techniques for massively multiplayer games. Our performance claims are backed by analysis using a simulation based on real game traces.