Distributed systems are notoriously difficult to implement and debug. One important tool for understanding the behavior of distributed systems is tracing. Unfortunately, effective tracing for moderndistributed systems faces several challenges. First, many interesting behaviors in distributed systemsonly occur rarely, or at full production scale. Hence we need tracing mechanisms which impose minimal overhead, in order to allow always-on tracing of production instances. Second, for high-speed systems, messages can be delivered in significantly less time than the error of traditional time synchronization techniques such as network time protocol (NTP), necessitating time adjustment techniques with much higher precision. Third, distributed systems today may generate millions of events per second systemwide, resulting in traces consisting of billions of events. Such large traces can overwhelm existing trace analysis tools. These challenges make effective tracing difficult. We present techniques that address these three challenges. Our contributions include (1) a low-overhead tracing mechanism, which allows tracing of large systems without impacting their behavior or performance (0.14 Â¿s/event), (2) a post hoc technique for producing highly accurate time synchronization across hosts (within 10/ts, compared to between 100 Â¿s to 2 ms for NTP), and (3) incremental data processing techniques which facilitate analyzing traces containing billions of trace points on desktop systems. We have successfully applied these techniques to two distributed systems, a cooperative caching systemand a distributed storage system, and from our experience, we believe our techniques are applicable to other distributed systems.