Transient stability simulation of a large-scale and interconnected electric power system involves solving a large set of differential algebraic equations (DAEs) at every simulation time-step. With the ever-growing size and complexity of power grids, dynamic simulation becomes more time-consuming and computationally difficult using conventional sequential simulation techniques. To cope with this challenge, this paper aims to develop a fully distributed approach intended for implementation on High Performance Computer (HPC) clusters. A novel, relaxation-based domain decomposition algorithm known as Parallel-General-Norton with Multiple-port Equivalent (PGNME) is proposed as the core technique of a two-stage decomposition approach to divide the overall dynamic simulation problem into a set of subproblems that can be solved concurrently to exploit parallelism and scalability. While the convergence property has traditionally been a concern for relaxation-based decomposition, an estimation mechanism based on multiple-port network equivalent is adopted as the preconditioner to enhance the convergence of the proposed algorithm. The proposed algorithm is illustrated using rigorous mathematics and validated both in terms of speed-up and capability. Moreover, a complexity analysis is performed to support the observation that PGNME scales well when the size of the subproblems are sufficiently large.