Ok, I am amazed: the phantom Xid idea worked! Only I didn't name it phantom Xid because that name has a bad history. So I named it MultiXactId. The implementation is finished; it only needs some more testing, making sure it deals correctly with wraparound, and that it correctly truncates SLRU segments.
To recap: the idea is to allow a row to be share-locked. This means somehow storing multiple TransactionIds in the tuple header. This is done by using a shared counter similar to TransactionId, which I have dubbed MultiXactId. Each MultiXactId is associated with variable-length storage in SLRU, on which the set of TransactionIds resides. This MultiXactId is stored in the tuple's Xmax, just like a TransactionId is stored in case of a SELECT FOR UPDATE.
I just posted the patch; probably Tom will have some disagreements with the way some things are done, but he already expressed approval of the general idea, so I expect that eventually this is going to be committed.
I feel somewhat ashamed that it took me two weeks (counting from the last blog entry) to complete the implementation. I hope not everything takes me this much, or I won't be having a lot done.
After this I'll return to the shared dependencies patch, and then I don't know what my next project will be ... maybe I'll continue trying to figure out a way to do the translation of the docs, which is badly needed.