Waiting time (where one processor is blocked while waiting for another) arises from a variety of sources in parallel programs, includlng communication, synchronization, load imbalance, and resource contention. Many tools can identify portions of the source code where waiting time arises and measure it during execution, but the programmer must infer the underlying cause of waiting time from other measurements. Carnival is a performance measurement and analysis tool that automates this inference process. Using traces of program executions, the tool identifies the differences in execution paths leading up to a synchronization point, and explains waiting time to the user in terms of those differences. It also supports several different types of performance profiles, which can be used to isolate and quantify important sources of waiting time. We present algorithms for characterizing waiting time in terms of execution paths, and describe implementations on the IBM SP2 and the SGI Challenge. We also present the Carnival user interface, and illustrate the functionality of the interface and the usefulness of waiting time analysis by identifying and explaining the sources of overhead in example applications.