  Multiparty session types (MSTs) are a type-based approach to verifying
communication protocols, represented as global types in the framework. We
present a precise subtyping relation for asynchronous MSTs with communicating
state machines (CSMs) as implementation model. We address two problems: when
can a local implementation safely substitute another, and when does an
arbitrary CSM implement a global type? We define safety with respect to a given
global type, in terms of subprotocol fidelity and deadlock freedom. Our
implementation model subsumes existing work which considers local types with
restricted choice. We exploit the connection between MST subtyping and
refinement to formulate concise conditions that are directly checkable on the
candidate implementations, and use them to show that both problems are
decidable in polynomial time.
