In this paper, we describe the development and the analysis of the Label Distribution Protocol (LDP) for Multiprotocol Label Switching System. We review the implementation issues that are required to construct the LDP for a gigabit switched router and propose a detailed design of the LDP. We present the detailed design using the Deviation Tree of the protocol state machine and a formal specification of the state machine using the process algebra. These specifications are based on the IETF standard. By analyzing the protocol behaviors of the Deviation Trees and the formal specification, we prove the interoperability, completeness, liveness, reachability, and the safety of the implemented LDP. We expect that the reliability would be improved using these analyses. With these proofs we expect the implemented LDP will be interoperable with other commercialized products. As a result we validate the protocol behaviors of the implemented LDP.