Aspects of the subject matter described herein relate to performing configuration in a multi-machine environment. In aspects, a client connects with one of a plurality of storage appliances. This storage appliance is sometimes called the coordinator appliance. Any of the storage appliances may act as the coordinator appliance. The coordinator appliance receives configuration data from the client and configures itself and the other storage appliances. During configuration, connectivity between the client and the coordinator appliance and between the coordinator appliance and the other appliances may be lost and re-established.