The reliability of protection systems has emerged as an important topic because protection failures have critical influence on the reliability of power systems. The goal of this research is to develop novel approaches for modeling and analysis of the impact of protection system failures on power system reliability. It is shown that repairable and non-repairable assumptions make a remarkable difference in reliability modeling. A typical all-digital protection system architecture is modeled and numerically analyzed. If an all-digital protection system is indeed repairable but is modeled in a non-repairable manner for analysis, the calculated values of reliability indices could be grossly pessimistic. The smart grid is emerging with the penetration of information-age technologies and the development of the Special Protection System (SPS) will be greatly influenced. A conceptual all-digital SPS architecture is proposed for the future smart grid. Calculation of important reliability indices by the network reduction method and the Markov modeling method is illustrated in detail. Two different Markov models are proposed for reliability evaluation of the 2-out-of-3 voting gates structure in a generation rejection scheme. If the model with consideration of both detectable and undetectable logic gate failures is used as a benchmark, the simple model which only considers detectable failures will significantly overestimate the reliability of the 2-out-of-3 voting gates structure. The two types of protection failures, undesired-tripping mode and fail-to-operate mode are discussed. A complete Markov model for current-carrying components is established and its simplified form is then derived. The simplified model can appropriately describe the overall reliability situation of individual components under the circumstances of complex interactions between components due to protection failures. New concepts of the self-down state and the induced-down state are introduced and utilized to build up the composite unit model. Finally, a two-layer Markov model for power systems with protection failures is proposed. It can quantify the impact of protection failures on power system reliability. Using the developed methodology, we can see that the assumption of perfectly reliable protection can introduce errors in reliability evaluation of power systems.