Web　Service　Negotiation　is　a　technology　that　autonomous　entities　reach　agreement　and　meet　both　needs　through　negotiation.　Web　Service　negotiation　mechanism　and　coordinated-negotiation　architecture　on　this　basis　have　become　hot　issues　of　current　research.　The　Coordinated-Negotiation　Architecture　of　Web　Service　Composition　based　on　Agent　is　a　relative　popular　one　in　current　architectures.　However,　there　are　some　problems　of　it:　unreasonable　use　of　time　and　data　link　resources　in　the　condition　of　multi-negotiation　concurrency,　which　results　in　inefficiency　of　negotiation;　lack　of　effective　processing　when　confronting　negotiation　failure.　In　this　paper,　we　put　forward　applying　asynchronous　communication　theory　to　the　process　of　Web　Service　Negotiation　and　extend　effective　processing　when　confronting　negotiation　failure　in　the　process　of　Web　Service　Negotiation,　present　a　new　Web　Service　Negotiation　Mechanism　and　a　new　Web　Service　Composition　Coordinated-Negotiation　Architecture　on　this　basis　so　as　to　solve　the　problems　above.　©　2010　IEEE.