So I have been spending some time learning about the basic concepts of online multiplayer programming. One that I have been recently thinking about is "lag compensation". I think this process goes by several different names, so I will explain what I mean so we are all on the same page. What I am referring to is the process of "rewinding" the server state to an earlier time to see if a bullet connected, a ball was hit, etc., taking into account what the player was actually seeing when they pressed the button considering things like "lerp" time, etc. 

My understanding is that this began as a solution to the problem of many headshots or other pixel-perfect collision detections missing due to latency and delay on entity movements for each client. So my question is, when do you need to actually do this type of lag compensation? Is it a requirement for almost all games to feel like they are playing correctly? Are games that don't specifically require pixel-perfect collisions such as Diablo III or World of Warcraft performing a step such as this? If a game like Zelda: A Link to the Past on the Super Nintendo had online multiplayer, would you imagine it would need to have lag compensation? It doesn't feel to me like 50 - 200ms would have a major impact on a game such as that in most circumstances, but I am not sure if I am missing something. 

Thank you! 

Lag Compensation is indeed the right term here, at least as it's commonly known based on the old Source Networking document: https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking#Lag_compensation

The purpose of lag compensation in this sense is to make the game feel more accurate for the shooter or viewer, by attempting to simulate the results as they would have appeared to that player. This is important in any situation where game entities move very fast relative to the latency between clients and the server, and where that difference between each side's perceived position for a given entity has a significant effect on gameplay.

So:

• typical first person shooter: players and weapons move very quickly, often across the field of vision - lag compensation is useful
• battleship simulator - it's still first person and shooting, but there's no chance of a battleship getting out of the way in 200 milliseconds - lag compensation is unnecessary
• online RPG - usually 3rd person, where aiming and timing is not critical and the area of effect can be fuzzy - no lag compensation necessary at all

Lag compensation is different from "input prediction" which is a bit of an awkwardly-named term for allowing a client to control its own entity's movement without waiting for full acknowledgement from the server. As this helps the player feel like the input is more responsive, this is much more widely employed, probably on almost every game type, except strategy games.

Like Kylotan said, it depends on how fast entities move relative to the latency. It should be easy to calculate the effects in most cases and state rewinding is not the only way to compensate for lag. For example, if entities generally move at a speed of 5m/s and you'd like to compensate for 200 ms of latency, you could extend the range of a fireball spell by 1m. You could extend the range both client and server side, or just server side. There are up and down sides to either approach. If you only extend the range server side, the client's input is less likely to rejected by the server, but you open yourself up to cheating to get that little bit of extra range. If you extend it on both sides the server will not reject as much for the range it was actually designed for, but you'll be more likely to be run into situations where you're client is within maximum range but the server rejects the input.

There are a lot of ways to go about it and the correct solution depends on the type of game and what you value most.

Thanks guys this makes a lot of sense! 

FWIW: to complement answers above, you may want to take a look at 

http://www.gabrielgambetta.com/client-server-game-architecture.html

and my http://ithare.com/mmog-rtt-input-lag-and-how-to-mitigate-them/

(they're describing the same things - but from somewhat different angles).