It seems as though the problem with determinism could be solved with random number seeding. If the server generates seeds, the two could stay synced even with random numbers.

The physics engine is a bit more difficult hurdle I suppose.