Frequency control is essential to maintain the stability and reliability of power grids. For decades, generation side controllers, e.g., governors and automatic generation controllers, have been used to stabilize the frequency of power systems, which incur high operational costs. In smart grids, utilizing demand response is an appealing alternative to control the system frequency at the demand side, which can reduce the dependency of grids on expensive generation side controllers. Despite of economic advantages, the frequency oscillation problem, which occurs when smart appliances simultaneously respond to the system frequency by varying their power consumptions, is the main barrier to realize demand response enabled frequency control in practice. In this paper, we investigate a new distributed control algorithm by randomizing smart appliances' responses to solve this problem. We provide a comprehensive analysis to characterize various impacts of the randomized demand response on the system frequency in terms of its mean and variance over time. Furthermore, based on the frequency dynamics analysis, we determine the average frequency recovery time, the average number of responded smart appliances, and the probability of frequency overshoot, which provide important guidelines for designing our control algorithm. Finally, we validate our analysis via simulations under practical setups.