We study the problem of frame synchronization over a discrete memoryless channel (DMC) in an asynchronous setup. A sync frame is transmitted at a random time V with a known distribution {αv} and entropy H. We seek to characterize the minimum average length or energy of the sync frame necessary for error-free frame synchronization, as H tends to infinity. We present a variable length sync frame, where the length of the sync frame is adapted based on H and {αv}, for the general arrival distribution and show error-free frame synchronization when the average sync frame length Ñ scales as Ω((H/α(Q)), where α(Q) is the synchronization threshold of the DMC. We then generalize the framework and study a tradeoff between Ñ and α(Q) for optimal frame synchronization and characterize the scaling needed of both Ñ and α(Q) with H. We illustrate our results with the AWGN channel and discuss the adapting sync frame length and symbol power for optimal frame synchronization. Finally, using numerical work and simulations, we evaluate the results under relaxed assumptions, including the imperfect knowledge of arrival distribution and symbol timing error.