Although others surely have much more experience and have thought about
this more, I still can't resist putting down my thoughts on this. The
topic sure is getting plenty of attention.
This problem doesn't seem that hard to me if you are willing to assume
that sequence numbers with occasional holes is ok. And that must be so,
otherwise how can you delete an accidental invalid contact (e.g. a
dupe)?
So assuming that an occasional hole is ok, proceed like this:
Each computer is pre-allocated a number in sequence. When a Q is logged
using the pre-allocated number, the computers interact to find out if an
allocated but unused number on another computer is lower than the one
just used, and therefore is a future out of sequence Q. If so, that
number is discarded and replaced with a new sequence number to prevent
the future out of sequence use.
Of course there is a small window for an error here. The lower number
could be used after the higher number due to the fact that the number is
used in the log before the arbitration is done. But in this case, with
any reasonable assumption about communication speed between the
computers, the lower number is used only a few seconds after the higher
number - simultaneously for all practical purposes. So you log them in
sequence number order rather than literal time order, and give them the
same timestamp if you happen to have crossed a minute boundary that
would otherwise give them different timestamps. Surely no reasonable
interpretation of the rules would call this time shift of a few seconds
a cheat. How closely synchronized do the rules expect multiple logging
clocks to be anyway - down to the second?
There are a couple of other issues I can think of. If one computer is
idle for a while, un-clever choice of how to deal out new numbers could
cause lots of holes, and while that might be "legal", it would not be
nice. For example if computer A is running and B is idle, and A logs #1
then tells B to discard #2, you can now allocate #3 to A and #4 to B, or
vice versa. The first choice is the right one, i.e. give the next number
to the computer that most recently logged, so that if the other computer
is idle, it gets a higher number which will not get used soon. Combine
this with logic that allows stealing in-sequence but unused numbers. So
continuing the previous example, if B is idle for a while, after A uses
#3, then he asks B for #4, which B agrees to since it doesn't need it.
Then A goes on to use #4 and B is allocated #5. This stealing continues,
and produces no holes, until B becomes active again.
So that's my take on this. Shoot it full of holes. I've had my fun.
Bill N7DZ
--
Submissions: ct-user@contesting.com
Administrative requests: ct-user-REQUEST@contesting.com
WWW: http://www.contesting.com/ct/
Questions: owner-ct-user@contesting.com
|