Over the past five years my group, in collaboration with wet-bench biologists, developed and validated asynchronous Boolean models of several signal transduction networks. Along the way we have encountered obstacles related to the lack of timing knowledge and the large size of the state space. In this talk I will present three methodologies we developed to overcome these obstacles. First, from a comparative analysis of several asynchronous update methods we concluded that updating a single, randomly selected node at each time instant offers the best combination of information and economy. Second, we developed a two-step network reduction method which was able to reduce the number of variables by 90% in two different systems without affecting their dynamic behaviors. Third, we proposed an integration of Boolean rules into graph theoretical analysis and showed that this semi-structural method can identify critical signal mediators on par with dynamic models.