Abstract : Checking the compatibility of service interfaces allows one to avoid erroneous executions when composing the services together. This task is especially difficult when considering interaction protocols, that is messages and their application order, in service interfaces. Although service compatibility has been intensively studied, in particular for discovery purposes, most of existing works return a Boolean result. However, if two services are incompatible, these approaches do not indicate whether the services are almost compatible or totally incompatible. This information is crucial if one wants to apply adaptation techniques, for instance, to successfully compose these services in spite of existing mismatches. In this paper, we propose a generic flooding-based techniques for measuring the compatibility degree of service protocols. We illustrate our approach with two compatibility notions, namely unspecified receptions and unidirectional complementarity. Our solution is fully automated by a prototype tool we have implemented.