I just heard on GitMinutes #07 that Mercurial will soon have a feature that records the relationship between old and new versions of changesets when a changeset is rewritten. This is a topic that I find very interesting, so I did some reading.
Each "obsolete marker" is a many-to-one record stating that changesets [A1,A2,...] obsolete changeset A. This information can be shared between repositories. The obsolete changeset is retained as long as any non-obsolete changesets depend on it, after which it can be discarded. (Though it wasn't clear to me how repository 1 can know whether repository 2 contains commits based on a commit that has been marked obsolete in repository 1; perhaps human-to-human communication is required?)
Unlike regular parent relationships, these markers have no implications for commit ancestry. That is, the fact that changeset A' obsoletes changeset A does not imply that commit A' includes all of the ancestors of commit A. Because of this, obsolete markers can be used even if changesets are reordered, split, or squashed--actions that cannot be represented in an ancestry-only DAG.
If I understand correctly, obsolete markers should really be thought of as relationships between changesets (i.e., the deltas introduced by commits) as opposed to the commits (and tree states) themselves. It appears that they are intended mostly for transitional use before the history has solidified, and not as a permanent part of the record.
Because obsolete markers introduce a new type of "history", they complicate the history model. There are new types of conflicts that can arise because of them, and such conflicts have to be resolved in new ways.
I'm very curious how obsolete markers pan out in practice. It's definitely a feature that is worth keeping an eye on.