A protocol for temporal synchronization of media signals with temporal components is used for digital watermarking and other applications. The synchronization protocol achieves initial synchronization by finding an initial synchronization key through analysis of a temporal media signal stream. It then uses features of the stream and a queue of one or more keys from previous frames to derive subsequent keys to maintain synchronization. If synchronization is lost due to channel errors or attacks, for example, the protocol uses the initial synchronization key to re-establish synchronization. In digital watermarking applications, the synchronization protocol is agnostic to the watermark embedding and reading functions.