This violates the promise of read committed. In RC, all transactions are supposed to see the most recently committed version of a record. The fact that it was a delete, then an insert is an implementation detail and "not my problem" as a DBA. At the time the transaction in session 1 commits, the most recently committed version of k='a' is v='c'. PostgreSQL, in the situation, seems to be operating in read uncommitted isolation level...session 2 is treating the uncommitted delete in session 1 as the most recent version.

I'd like to give PostgreSQL the benefit of the doubt here, but this behavior seems fundamentally incorrect to me.