Authentication as a security key issue is required for securing the inter-vehicle communication. Mostly, authentication schemes that depend on the network infrastructure Road Side Unit (RSU) had been proven to have low computation and communication overhead. RSUs may become unavailable due to congestion or failure conditions. Replicating authentication service offered by RSUs to trusted vehicles in their ranges may present novel alternative to support the availability of such services. A complement to our previous replication protocol Central Push-based Replication Protocol (CPRP) is presented in this work. Two new replica allocation techniques are proposed to spawn new replicas in order to improve the authentication service availability that are offered from RSUs. The optimality (Correctness) of these techniques has been evaluated with different ratios of RSU failures in different realistic scenarios. The results showed that both techniques improve CPRP in increasing the authentication services availability.