Jack,
After working over Baumer's paper a bit, I don't understand the fault
handling bits of the protocol, in chapter 4. (Wording quoted here are all
from section 4.1, the overview):
- "When a keyserver detects a gap in the sequence number, it sends a
_request_ message to another keyserver, ..." When is the gap checked
for? Upon receipt of an update, no doubt; what about upon receipt of "a
_request_ message"?
We thought that the updates and heartbeats should ensure eventual
reliable delivery. While it might speed up the synchronization by also
acting on requests for unknown sequence numbers, this will require more
bookkeeping at each server. A server willing to seek out for new
sequence numbers based on an incoming request will have to make sure
that it doesn't react to further incoming requests by generating another
request, to prevent livelocks. But other than that, the decision about
the two possible behaviors can be left to the discretion of the
individual implementations (they will still interoperate correctly,
IMHO).
- "... the sequence number ..." Is that the number of the last
contiguous
known event, the first missing, the last missing, or the first received
noncontiguous? In general, there may be missing gaps, not merely single
events (indeed, this seems more likely to me). ("The oldest missing
sequence number" seems like a good choice, with the implication that this
one and all subsequent known events be transmitted.)
Further down, request messages are described to basically contain an
enumeration of missing sequence numbers, represented in either of three
compact forms (ranges, bitmaps, and "everything above x")
- "Then the Nearest Neighbour sends the information..." What if the NN
is
also missing the requested info? Mention of deadlock elsewhere suggests
the NN might in turn requery its NN at this point, but this is nowhere
explicit.
The node detecting a missing sequence number will look for the NN having
the information using expanding multicast rings (although building rings
based on increasing TTL will not be too effective in IPv4, where both
scope and TTL are encoded in the TTL). Servers receiving a multicast
request message should not answer if they do not have (part of) the
requested information. Whoever responds first will be considered the NN
for that operation (see 5.8). If all fails, it may revert to the
originator.
- During this period (while a _request_ is pending from the NN), what is
the behavior of the server with respect to the request itself? Does it
retry its request periodically, and/or after a timeout? Should the server
crash in the interregnum, is it obligated to restore itself in some state
that will accept (or re-request) this info? Or does it wait until yet one
more event arrives from the originator? Does it continue to accept and
apply new server-server updates from this originator? From other originators?
Expanding MC rings require some timeout mechanism during the expansion.
If a search turns out to be fruitless, the server can schedule a search
for a later time (preferrably some exponential backoff), or can wait for
the next heartbeat to occur, which should trigger the next search.
On a restart, the server can locally check for sequence gaps.
Additionally, it can search for someone responding to a
RequestSequenceCheck (i.e., actively soliciting for a unicast heartbeat
message), or simply wait for the next heartbeat to arrive.
- During this period, does it continue to serve uploads and requests
from
users? Does it attempt to apply the updates? (Note that some events, from
beyond the gap, from other servers, or from users, may not be possible to
apply, without the missing data - a new user ID added but lost, for
example, means a subsequent signature on that ID can not be applied - and
may not come even from the same originating server, so the potential
extends over all updates.)
Yes. Since users have to submit entire keys, there will be no missing
information. But it can occur that this server is uploaded a packet
which (unknown to us) another server has already issued an ID for, in
which case a single packet will receive a second ID (this is expected to
occur in rare cases). Since the linking between signatures and UIDs and
public keys occurs by sending out the higher-level elements also,
stalls as you describe them should not occur.
- How does the distributed database detect and communicate the case
where
a request to an NN is for some sequence number that in fact does not exist?
I'm particularly thinking of a potential global denial-of-service attack,
by sending a nonsensically-high sequence number into the mbone. All
keyservers then query their NN, but none know the answer. There is no
algorithm apparent here to recover (not to say it couldn't exist, but I
don't find it here).
This is true for both request- and update-/heartbeat-triggered
resynchronization and is dealt with in section 5.7, together with other
attacks. The originator can be queried for a signed message containing
the highest sequence number. This assumes that the servers know each
others public key. The signature does not need to be created "live", to
avoid further DoS attacks, but has a lifetime associated with it.
There is also support for cryptographically challenged servers, but
they obviously cannot protect their sequence numbers.
-Marcel
pgp6ck02vLUiB.pgp
Description: PGP signature