Dans le cadre des TICSP (Probleme de Satisfaction de Contraintes pour l'algebre d'Intervalles de Temps), nous avons propose une amelioration de l'algorithme d'Allen. A partir de la composition d'Allen, nous avons propose une composition entre 4 n uds. Puis, sur la base de cette composition, nous avons developpe un algorithme incremental pour la 4- coherence ramenant la complexite a l'ordre O(n3). En utilisant la generalisation de la composition entre 4 n uds a la composition entre k n uds, nous avons propose un algorithme de k-coherence avec une complexite temporelle en O(nk-1). Le passage des Problemes de Satisfaction de Contraintes (CSP) aux Problemes de Satisfaction de Contraintes Distribues (DCSP) pose le probleme du passage de l'individuel au collectif. Ce passage a fait l'objet de diverses extensions du cadre CSP a des DCSP. Dans ce cadre et a partir de l'algorithme Intelligent BackTracking Distribue (DIBT), nous avons propose une Generalisation Optimale en envoi de messages (OGDIBT). DIBT n'etant pas complet. Dans ce memoire, une etude de la completude d'OGDIBT est proposee et une version complete y est donnee."