A method is performed by a master network device among network devices of a cluster. The master network device receives cluster configuration information including a set of Internet Protocol (IP) addresses and a pool of port blocks associated with the IP addresses. Each port block includes multiple ports, and the pool of the port blocks is to be shared across the network devices for port address translation. The master network device divides the port blocks in the pool into multiple buckets. The master network device allocates to each network device in the cluster a corresponding one of the buckets, and reserves each bucket that is not allocated for allocation to a potential new network device. When a new network device joins the cluster, the master network device allocates to the new network device the port blocks from a corresponding one of the reserved buckets.