Methods, systems, and computer program products are included for performing tracing in a distributed environment. An example method includes determining that a first span corresponds to a client span kind and that a second span corresponds to a server span kind. The first span is cached in association with a span identifier. An identifier associated with the second span is matched to the span identifier associated with the first span. Based on the matching, dependency information is generated corresponding to the first span and the second span.