Modern distributed systems may nowadays consist of hundreds of thousands of computing elements, and system design will go hand-in-hand by means of a partly bottom- up approach in which computing elements are glued together into a full-fledged system that can scale beyond imagination. This new kind of scalability and complexity poses unprecedented challenges for the traditional Binary Decision Diagram (BDD)- based reliability evaluation. In order to evaluate the complex structure functions of largescale distributed systems with limited computational resources, a common practice is to truncate the BDD. Using the truncated BDD (much smaller than exact BDD), approximate reliability can be calculated. In this paper, an efficient BDD truncation algorithm is proposed, which adopts a lazy mechanism and a writeback mechanism to reduce time and space consumption of truncation by means of implementing the sharing of sub-BDD. Two approximate reliability evaluation methods are proposed, and the corresponding truncation error estimators are developed based on the truncation limits or the bounds of exact reliability. A set of evaluation procedures are developed for different evaluation requirements.