New state tables

[Peter Furniss <peter.furniss@choreology.com>]

Well at last I'm sufficiently confident in the state tables that I'm letting
them out.  They, and the revised explanation, and the abstract message set
will be incorporated in the next draft from Alastair and me tomorrow. This
should also include the xml messages from Bowstreet.

Quick summary of the state table changes


there are now just two tables - one for superior, one for inferior

The query messages (*_STATUS/*/y) merely ask for a response and do not
require one.  In consequence of this, more or less all messages can be sent
repeatedly - so if superior sent PREPARE, and suspects that it got lost, it
resends it.

As further corollary of that, in most cases the sides just resend the last
message, and not a *_STATUS message if they want to nudge the other side.

(the above enormously reduces the number of states. It isn't really
necessary to have the separate *_STATUS/*/y and *_STATUS/* events - they are
distinguished so as to make the simulator keep track of whether it should
reply to an incoming *_STATUS. This might be better handled as a separate
piece of state information)

There are still the various disruption events, which identify the states to
in which a side may find itself if it loses some state information.

There is no longer a VOTE with different values, but just READY. If the
inferior ever determines that it is going to cancel, it sends CANCELLED,
whether before (and instead of) sending READY, after sending (=heuristic or
expired participant timeout) or in response to CANCEL.

CONFIRMED has to distinguish between whether it is sent as a result of an
autonomous confirmation or in reply to a real one. This derives from the
need catch autonomous confirmations from participants that never got
enrolled, and to distinguish these from very late CONFIRMED replies.

MIXED has been added, when the inferior discovers it has a (heuristic) mix
below it.

REQUEST_CONFIRM is included in these tables - it is effectively a one-phase
commit (which consequently can only be sent to an "only child" inferior.).
REQUEST_CONFIRM causes some events to be possible which otherwise don't
happen (some still marked by excel comments)

The "default cancel" (READY, will cancel on timeout, and don't tell it if
superior does cancel) has been included. The corresponding "default confirm"
has NOT been included as it is believed to be impossible to avoid undetected
and unreported contradictions. (essentially, given a failure at the
(in)appropriate moment, the superior would be content that the atom has
cancelled and the inferior content that it has confirmed and no-one ever
checks up.)  Defaut cancel would seem to be much more likely to be used
anyway.


I ran versions of this earlier in the week (before adding REQUEST_CONFIRM)
and they were faultless over 5 million trials. With REQUEST_CONFIRM there
are some events that can occur but are very hard to trigger (CONTRADICTION
in n2 seems to have an occurence on the order of 1/5,000,000 )

The failure assumptions are a bit better now - as well as the disruptions in
the table, the simulator can cause loss of messages in any state, without
other state change. The results were always either consistent confirm,
consistent cancel, contradiction reported to the superior.  With the
assumption that messages that are delivered are delivered in the order sent,
then it never enters an empty cell, every non-empty cell is used and it
never reports false positive contradictions.  If the assumption about
ordering is dropped, the receiver should ignore any empty cell events -
there is then a possibility of false positive contradiction detection after
confirmation, but this only occurs if the confirm log is removed (Z1 -> Z)
during the network latency time.

(REQUEST_CONFIRM also makes false positive contradiction reporting possible
in some failure cases)

I've enclosed both pdf (one page each) and the excel.  The excel shows some
extra columns which are used by the simulator to work out what happened.

Peter

------------------------------------------
Peter Furniss
Technical Director, Choreology Ltd
email:  peter.furniss@choreology.com
phone:  +44 20 7670 1679
direct: +44 20 7670 1783
mobile: 07951 536168
13 Austin Friars, London EC2N 2JX

btp_state.pdf

btp_state.xls