The present invention provides a network support mechanism, called Sync-VPN, that is transparent to real-time, multi-user distributed applications, such as online multi-player games in which the order of player actions is critical to the outcome. The invention uses a client/server application model, where a server coordinates state updates based on action messages sent by clients. The invention builds on bandwidth-quaranteed VPN service to ensure predictable packet delay and loss characteristics, thereby providing predictable packet service, state update fairness, and player action fairness. A Sync-out mechanism synchronizes delivery of state updates to all players enabling them to react to the same update fairly. A Sync-in mechanism processes action messages from all players in a fair order based on real-time occurrence. Sync-VPN employs a round-trip time estimation algorithm essential to message latency estimation in the Sync-out and Sync-in mechanisms.