Presented herein are techniques for detecting anomalies in micro-service communications that are indicative of security issues/problems for the application. More specifically, a computing device receives a plurality of micro-service communication records each associated with traffic sent between pairs of executables (nodes) that are related to a micro-services application. Each of the micro-service communication records includes a time series entry and an associated trace sequence identifier and each of the micro-service communication records are generated during a time period. The computing device analyzes the plurality of micro-service communications to detect possible anomalous communication patterns associated with the micro-services application during the time period.