  We consider the `one-shot frame synchronization problem' where a decoder
wants to locate a sync pattern at the output of a channel on the basis of
sequential observations. We assume that the sync pattern of length N starts
being emitted at a random time within some interval of size A, that
characterizes the asynchronism level between the transmitter and the receiver.
We show that a sequential decoder can optimally locate the sync pattern, i.e.,
exactly, without delay, and with probability approaching one as N tends to
infinity, if and only if the asynchronism level grows as O(exp(N*k)), with k
below the `synchronization threshold,' a constant that admits a simple
expression depending on the channel. This constant is the same as the one that
characterizes the limit for reliable asynchronous communication, as was
recently reported by the authors. If k exceeds the synchronization threshold,
any decoder, sequential or non-sequential, locates the sync pattern with an
error that tends to one as N tends to infinity. Hence, a sequential decoder can
locate a sync pattern as well as the (non-sequential) maximum likelihood
decoder that operates on the basis of output sequences of maximum length A+N-1,
but with much fewer observations.
