Martijn van Oosterhout <kleptog(at)svana(dot)org> writes:
> Well, there has to be something, since an UPDATE in Read Committed mode
> simply doesn't have any locks that can deadlock.
You're mistaken; it takes a row lock on each row it updates. I'm not
sure why the two UPDATEs are visiting the same rows in different orders,
but if they do the failure is certainly possible.
regards, tom lane