The Fair-Order Service of the present invention delivers action messages to the server as soon as it is feasible. Because action messages from different players exhibit different reaction times with respect to an update message, the Fair-Ordering Service executed at the server dynamically enforces a sufficient waiting period on each action message to guarantee the fair processing of all action messages. In reality, the waiting period at the server is bounded because of the real-time nature of interactive games. The algorithms that offer Fair Ordering Service take into consideration delayed and out-of-order action messages. When action messages corresponding to multiple update messages are interleaved, the Fair-Ordering Service matches the action message to the appropriate update message. It accomplishes this by maintaining a window of update messages and using the reaction times for an action message for each of the update messages in the window. This enables state changes at the game server to be performed with fairness to all the players. The Fair-Order Service invention is based on a framework that uses a proxy architecture making it transparent to any specific game application. The service is well suited to client-server based, online multi-player games, where a fair order of player actions is critical to the game outcome.