Although multithreading can improve performance, it is a source of nondeterminism in application behavior. Existing approaches to replicating multithreaded applications either synchronize replicas at interrupt level, at the expense of performance, or use a nonpreemptive deterministic scheduler, at the expense of concurrency. This paper presents a loose synchronization algorithm for ensuring deterministic replica behavior while preserving concurrency. The algorithm synchronizes replica threads only on state updates by enforcing an equivalent order of mutex acquisitions across replicas.