In some games/engines (such as Source), the server compensates for latency by applying player inputs in the past. Whenever the server receives a player's input for a frame, it rewinds the game to the frame that input was intended for, applies the player input, then simulates the game again up to the current time. The server needs to do several times as much game-logic computation as the clients, as each frame can be simulated many times - so it seems like this would not scale well to many clients or processing-intensive games.
However, we can turn this around. If the client input for a particular frame always arrives before the server simulates that frame, then the server never needs to rewind - it only ever simulates each frame once.
In order for a player's input to reach the server before the frame that the player entered it on, the client needs to run in advance of the server. If a particular client has a latency of 250 ms, then it must simulate tick 51388 at least 250ms before the server simulates tick 51388.
Therefore, the client must be predicting the game state several ticks in advance. Every time the client receives an update from the server, the client rewinds the game, applies the update, and fast-forwards up to the current time.
If n is the number of clients, then the clients each do O(n) extra work per tick to support lag compensation, instead of the server doing O(n^(2)) extra work per tick (assuming the game state size scales as O(n)).
I don't know of any games that actually do this. What are the problems with this approach?