As indicated herein, a cloud provider network 203 can be formed as a number of regions 306, where each region 306 represents a geographical area in which the cloud provider clusters data centers 309. Each region 306 can further include multiple (e.g., two or more) availability zones (AZs) connected to one another via a private high-speed network, for example, a fiber communication connection. An AZ may provide an isolated failure domain including one or more data center facilities with separate power, separate networking, and separate cooling from those in another AZ. Preferably, AZs within a region 306 are positioned far enough away from one another such that a same natural disaster (or other failure-inducing event) should not affect or take more than one AZ offline at the same time. Customers can connect to an AZ of the cloud provider network 203 via a publicly accessible network (e.g., the Internet, a cellular communication network).