Over the past decade, numerous systems have been proposed to detect and subsequently prevent or mitigate security vulnerabilities. However, many existing intrusion or anomaly detection solutions are limited to a subset of the traffic due to scalability issues, hence failing to operate at line-rate on large, high-speed datacentre networks. In this paper, we present a two-level solution for anomaly detection leveraging independent execution and message passing semantics. We employ these constructs within a network-wide distributed anomaly detection framework that allows for greater detection accuracy and bandwidth cost saving through attack path reconstruction. Experimental results using real operational traffic traces and known network attacks generated through the Pytbull IDS evaluation framework, show that our approach is capable of detecting anomalies in a timely manner while allowing reconstruction of the attack path, hence further enabling the composition of advanced mitigation strategies. The resulting system shows high detection accuracy when compared to similar techniques, at least 20% better at detecting anomalies, and enables full path reconstruction even at small-to-moderate attack traffic intensities (as a fraction of the total traffic), saving up to 75% of bandwidth due to early attack detection.