Still, he brings up a good point. If the source of non-determinism is known to be exactly in the physics engine, maybe it's possible to share the global physics state every once in a while.

I don't know much about game network code, but is this feasible at all? Another post brought up the reason for using lock-step networking is because of "thousands" of units, so I assume the biggest data is the physics data (x,y,z velocity, etc of said units).

If some physics errors could be tolerated for a few ticks, maybe a binary search of the gamespace could be used to figure out where the error came from, and sync up the game state in that area. Could be fairly low bandwidth right?