In this work we present a totally asynchronous distributed algorithm for the problem of achieving arc-consistency in a network of constraints. The algorithm is designed for multicomputer systems. Since the number and size of messages are two factors of major concern when solving a problem distributively we have paid particular attention to designing the algorithm in a way that tends to reduce their number and size. Our approach relies on identifying whether a message can be suppressed without affecting the operation of the process to which it was addressed. This has the effect of keeping the number of exchanged messages low at a cost of some small extra computation time.