The present work is aimed to develop and analyze a novel model for distributed stateful intrusion detection able to scale in order to keep up with the pace of high speed network links. More precisely, in this work we make the following contributions: - We introduce a novel architecture for the distributed matching of stateful network-based signatures. - We present a novel algorithm that allows for the detection of complex, stateful attacks in a distributed fashion. - We provide a precise characterization of the bottlenecks that are inherent to the distributed matching of stateful signatures in the most general case. - We developed optimizing to reduce the impact of these bottlenecks and improve the performance of distributed detection. - We describe a working, yet demonstrative implementation of the system based on the Snort intrusion detection engine - We provide an evaluation of the implemented system on a real-world testbed