You seem to have explained everything yourself. But, in case you need someone agree / disagree with that: Yes, your thoughts all seam reasonable.
As you do not wait for all players inputs before start simulating the world, you will run into those problems. You can not solve this, as you don't have the information (what each player does) before the network has transferred it.
So you only can "guess" what will happens and show this to your players, which is like predicting future (you might have luck or not). Or, you show only what is already for sure which will cause the maximum lag of all users to effect all users experience.
The only thing you can do about this is to improve your prediction algorithm for a user. E.g. detect movement patterns in acceleration, deceleration. But you'll never get it to perfection...
Note, that if a user only pretends to be lagging (network lag) he might see his "simulated" future. So the user might cheat. To balance the chances, you should delay the information (what other players did) sent from the server to each user by the detected lag (minus the minimum lag of all players).
EDIT #1
To answer your question in the comment below:
Well, the question might be hidden in there, but I wanted to ask is which approach is better, to re-simulate world on the server when user's input arrives or discard the timestamp info. Both have their pros and cons, I guess it depends on the situation. I was just wondering if there is another solution that I might be missing –
In the environment of a 3D-Shooer game:
Dropping the Timestamps: This is bad for the player with longer lags, as something different happens than he actually commanded. His commands will be executed in the future. You stop pressing "forward" and your actor stops some time later. You maybe shoot while seeing the object in the cross hair, but its executed when it already moved further. The players with longer lags know this and can adapt to this. They can release the forward key earlier or shoot a bit earlier than they would normally need. This is like driving a car, where you need to turn the wheel some meters in advance if you drive very slow... This is in a way acceptable to the lagging player, as he knows that he causes the problem himself. He also cant cheat by even increasing his lag.
Simple Re-Simulation when releasing information immediately: This is bad for all players with fast connections, as the lagging players just "beam" from one position to the other and they don't have a chance to know where he really is, while the lagging players can more easily aim their targets (they immediately see their correct opponents positions).
Delayed information releasing: You can also wait until all clients have send their current "actions" to the server and then distribute the whole information to all clients and simulate it. This gives a consistent state of the game at all clients, without the need for re-simulation. The client programs may of course "predict" the future and display it. This causes all players to suffer from the largest lag, but equalizes the chances of the players a bit. The lagging players still have some more problems, as their update-interval is longer. This means the time needed to send the next update from the server to this client is longer, and the player has a longer time in which he only sees the "prediction". But as long this period is short enough, this shouldn't be a real problem.
You can also do a combination of these methods. You can delay information releasing up to some limit (e.g. 50 ms and then start to drop "timestamps"). So you wait until all players have send their next actions -or- some timeout (e.g. 50 ms) is reached and then distribute them to the player together with the timestamp registered at the server. The server just simulates this. If an action is arriving too late at the server it is executed within the next round / simulation tick. The result is, that up to the limit (e.g. 50 ms) the player will have a synchroneous play, the server does not need to resimulate and only players with longer delays will have re-simulations at their client and will actually suffer from the problem. It also enables to have a quicker update period, if all players have a shorter ping that the limit (e.g. 50ms).
Other Game Types...
In games which are more cooperative in nature and lots of players (as MMORPGs for example) the lag for all other players should be at least be limited to a reasonable amount. You'll always have players with slower connections, so they would at the end define the speed of the whole simulation. Depending on the type of game, the acceptable lag can be up to 400ms without being noticed by the players. This might especially work for real time strategy games... Especially in real-time strategy games repeatedly re-simulating and excessive "beaming" of actors would not be acceptable, if this is happening for all players. "What happens if I delay commands for x milliseconds in this game?" is what matters. For example in a real time strategy game it would even sound logical that it takes some time to tell the acting unit what it shall do, then it maybe needs to plan the route and finally starts walking. So a short delay won't disturb to much.
