diff -r 760c0d67ce5e -r 06f075836010 mercurial/discovery.py
--- a/mercurial/discovery.py	Tue Jan 15 02:59:12 2013 +0100
+++ b/mercurial/discovery.py	Tue Jan 15 02:59:12 2013 +0100
@@ -268,7 +268,7 @@
     allmissing = set(outgoing.missing)
     allfuturecommon = set(c.node() for c in repo.set('%ld', outgoing.common))
     allfuturecommon.update(allmissing)
-    for branch, heads in headssum.iteritems():
+    for branch, heads in sorted(headssum.iteritems()):
         if heads[0] is None:
             # Maybe we should abort if we push more that one head
             # for new branches ?
@@ -312,7 +312,7 @@
             unsynced = True
         if len(newhs) > len(oldhs):
             # strip updates to existing remote heads from the new heads list
-            dhs = list(newhs - bookmarkedheads - oldhs)
+            dhs = sorted(newhs - bookmarkedheads - oldhs)
         if dhs:
             if error is None:
                 if branch not in ('default', None):