One of the key issues with decentralized online multi-player games is ensuring fairness of game play despite different network latencies. One approach is to follow a "lock step" scheme that prevents any player from acting upon a message until that message is received by all the players. In this paper, we present a fair synchronization protocol (FSP) that enforces fairness and is more efficient than a lock-step scheme. The basic FSP protocol is susceptible to cheating. Therefore, we add a cheat prevention mechanism as an enhancement. We implement the enhanced protocol, the Cheat Proof Protocol (CPP), in a simple game environment and deploy it on the PlanetLab. The results indicate that the CPP is effective in enforcing fairness while preventing cheating.