Simultaneous index creates on different schemas cause deadlock?

In our production environment, we separate each shard out into its own
schema to give us flexibility in shard location. This leaves us with a
lot of schemas hosted on a relatively smaller set of servers.

With so many schemas, database migrations started to take a long time
to run across all of them. To address this, we introduced some
parallelism in our migration-running process. So we'll have several
processes hopping across the shards at once performing DDL operations
and what have you. This helped our migration runtime considerably.

We had an odd situation crop up recently that confused me. The
migration we were running included a "CREATE INDEX CONCURRENTLY" (a
fairly common occurrence for us), and as it ran across our environment
we hit several deadlocks of the following form:

> Process 3445 waits for ShareLock on virtual transaction 5/27569425; blocked by process 3440.
> Process 3440 waits for ShareLock on virtual transaction 13/22769556; blocked by process 3445.

For every deadlock, each process involved was running one of our
"CREATE INDEX" statements.

I've managed to reproduce this behavior with a simple little ruby
script that creates 10 schemas, each with a 10k row table, and then
attempts to index those tables in parallel. For me, this deadlocks
every time:

https://gist.github.com/phinze/f38578d39f9e0ed4fd25

This is what confused me: since the indexes are each being created in
completely independent schemas, what resource could possibly be in
contention to cause these deadlocks?

Thanks for your time,

Paul