A one-pass recognition algorithm is presented to solve the membership problem for rational trace languages. The algorithm is detailed through the formal specification of the Buffer Machine, a non-deterministic, finite-state automaton with multiple buffers that can solve the membership problem in polynomial time. The performances and characteristics of the proposed solution are evaluated on a testbed implementation using pseudo-random traces, strings, languages and dependency relations.