Distributed trace recording and replay is based on tracing execution of a first entity at a first computer system, while also concurrently and independently tracing execution of a second entity at a second computer system. The traces include corresponding orderable events that occurred during execution of the entities at their corresponding computer systems, and are recorded at fidelity that enables complete replay of the recorded execution of the entities. Each trace includes information that at least partially orders, among the respective orderable events, sending or receipt of at least one message passed between the entities.