With the advent of Smart Grids and advanced communication technologies, the self-healing scheme has become a desirable function of the operation and planning of electrical distribution systems (EDSs). In the presence of a permanent fault, an optimized self-healing scheme minimizes the unsupplied demand while maintaining the faulted section of the network isolated. The service restoration of the self-healing scheme is a combinatorial optimization problem whose computational complexity grows exponentially with the number of binary variables. To resolve this issue, a distributed optimal service restoration strategy is developed based on the alternating direction method of multipliers (ADMM). The service restoration problem is formulated as a mixed-integer second-order cone programming (MISOCP) problem. The decision variables of the problem are the status of the remote-controlled switches, load zones and load shedding at each controllable demand. Operational constraints, such as current and voltage magnitude constraints, distributed generation (DG) capacity constraints and radial topology constraints, are respected in the optimization problem. Through the ADMM, the optimization problem is distributed among the zones of the EDS, without requiring a central controller. Two test systems, an unbalanced 44-node system and the IEEE 123-node system, were used to conduct case studies. Results show that the proposed method can provide optimal service restoration solutions in reasonable time without a central controller.