I'm not too familiar with postgresql, but isn't that serializable snapshot rather than serializable? I'm pretty sure all RDMBs have deadlocks in serializable. But in serialiable snapshot, a transaction doesn't deadlock, but simply fails.
see above comment from abadid - its entirely possible to impose a global ordering of all transactions either up front or retroactively without admitting deadlocks.