Dans le cadre des TICSP (Probl me de Satisfaction de Contraintes pour l'alg bre d'Intervalles de Temps), nous avons propos une am lioration de l'algorithme d'Allen. A partir de la composition d'Allen, nous avons propos une composition entre 4 noeuds. Puis, sur la base de cette composition, nous avons d velopp un algorithme incr mental pour la 4- coh rence ramenant la complexit l'ordre O(n3). En utilisant la g n ralisation de la composition entre 4 noeuds la composition entre k noeuds, nous avons propos un algorithme de k-coh rence avec une complexit temporelle en O(nk-1). Le passage des Probl mes de Satisfaction de Contraintes (CSP) aux Probl mes de Satisfaction de Contraintes Distribu s (DCSP) pose le probl me du passage de l'individuel au collectif. Ce passage a fait l'objet de diverses extensions du cadre CSP des DCSP. Dans ce cadre et partir de l'algorithme Intelligent BackTracking Distribu (DIBT), nous avons propos une G n ralisation Optimale en envoi de messages (OGDIBT). DIBT n' tant pas complet. Dans ce m moire, une tude de la compl tude d'OGDIBT est propos e et une version compl te y est donn e.