Dan Ports <drkp(at)csail(dot)mit(dot)edu> wrote:
> On Wed, Jun 01, 2011 at 05:09:09PM -0500, Kevin Grittner wrote:
>> Published papers have further proven that the transaction which
>> appears to have executed last of these three must actually commit
>> before either of the others for an anomaly to occur.
>
> We can actually say something slightly stronger than that last
> sentence: Tout has to commit before *any* other transaction in the
> cycle. That doesn't help us implement SSI, because we never try to
> look at an entire cycle, but it's still true and useful for proofs
> like this.
I didn't know that, although it doesn't seem too surprising. With
that as a given, the proof can be quite short and straightforward.
> Now, supposing Tin is read-only...
>
> Since there's a cycle, there must also be a transaction that
> precedes Tin in the serial order. Call it T0. (T0 might be the
> same transaction as Tout, but that doesn't matter.) There's an
> edge in the graph from T0 to Tin. It can't be a rw-conflict,
> because Tin was read-only, so it must be a ww- or wr-dependency.
> Either means T0 committed before Tin started.
>
> Because Tout committed before any other transaction in the cycle,
> Tout has to commit before T0 commits -- and thus before Tin
> starts.
If we're going to put this into the README-SSI as the proof of the
validity of this optimization, I'd like to have a footnote pointing
to a paper describing the "first commit in the cycle" aspect of a
dangerous structure. Got any favorites, or should I fall back on a
google search?
-Kevin