The paper considers automatic, specification-based detection of failures (differences between observed and specified behavior) in external behavior of software systems. The external behavior is recorded in traces, which are analyzed for the presence of failures. The paper describes a novel failure detection technique. The technique is applicable to multi-user systems which are reactive, session-oriented and specified in formalisms based on communicating extended finite state machines. It separates the failure detection concerns into two parts, the detection of failures directly noticeable by individual users, and the determination whether the individually correct local behaviors are globally consistent with the specification. An experimental evaluation of the technique on the control program for a small telephone exchange is also presented.