diff --git a/mercurial/httppeer.py b/mercurial/httppeer.py
--- a/mercurial/httppeer.py
+++ b/mercurial/httppeer.py
@@ -282,17 +282,17 @@
         # Tell the server we accept application/mercurial-0.2 and multiple
         # compression formats if the server is capable of emitting those
         # payloads.
-        protoparams = []
+        protoparams = set()
 
         mediatypes = set()
         if self._caps is not None:
             mt = self.capable('httpmediatype')
             if mt:
-                protoparams.append('0.1')
+                protoparams.add('0.1')
                 mediatypes = set(mt.split(','))
 
         if '0.2tx' in mediatypes:
-            protoparams.append('0.2')
+            protoparams.add('0.2')
 
         if '0.2tx' in mediatypes and self.capable('compression'):
             # We /could/ compare supported compression formats and prune
@@ -300,10 +300,10 @@
             # For now, send the full list to the server and have it error.
             comps = [e.wireprotosupport().name for e in
                      util.compengines.supportedwireengines(util.CLIENTROLE)]
-            protoparams.append('comp=%s' % ','.join(comps))
+            protoparams.add('comp=%s' % ','.join(comps))
 
         if protoparams:
-            protoheaders = encodevalueinheaders(' '.join(protoparams),
+            protoheaders = encodevalueinheaders(' '.join(sorted(protoparams)),
                                                 'X-HgProto',
                                                 headersize or 1024)
             for header, value in protoheaders:
diff --git a/mercurial/sshpeer.py b/mercurial/sshpeer.py
--- a/mercurial/sshpeer.py
+++ b/mercurial/sshpeer.py
@@ -168,10 +168,10 @@
 
     Returns a list of capabilities that are supported by this client.
     """
-    protoparams = []
+    protoparams = set()
     comps = [e.wireprotosupport().name for e in
              util.compengines.supportedwireengines(util.CLIENTROLE)]
-    protoparams.append('comp=%s' % ','.join(comps))
+    protoparams.add('comp=%s' % ','.join(comps))
     return protoparams
 
 def _performhandshake(ui, stdin, stdout, stderr):
@@ -626,7 +626,8 @@
     # capabilities.
     if 'protocaps' in peer.capabilities():
         try:
-            peer._call("protocaps", caps=' '.join(_clientcapabilities()))
+            peer._call("protocaps",
+                       caps=' '.join(sorted(_clientcapabilities())))
         except IOError:
             peer._cleanup()
             raise error.RepoError(_('capability exchange failed'))