In one embodiment, a first path computation element (PCE) operates between first and second network domains, and is adapted to service requests from path computation clients (PCCs) in at least the first domain. In response to a backup event (e.g., failure of a second PCE), a backup PCE in the second domain may be informed of path computation information for the first domain used by the first PCE, and tunnels may be bi-directionally established between the first PCE and the backup PCE. Once the tunnels are established, the backup PCE may be advertised into the first domain, and the backup PCE may operate to load balance service requests for the first domain through the bi-directionally established tunnels.