He could just interprete code on clients :)

You have N players == N computers to simulate. Assign randomly 5 computers to each player to emulate. Choose the result that majority of clients return and optionally punish cheaters.

EDIT: apparently simulation will go on even when players log out, so each connected client may need to simulate 100 in-game computers to account for that. Still less resource intensive than running everything on the server. But Notch thought about that much longer and surely have great reasons for his architecture.