A technique for data placement in a distributed system that takes into account fault tolerance. Data placement is performed in which data objects, and possibly replicas thereof, are assigned to nodes within the distributed system. The resulting placement is then tested to determine whether the system provides desired performance under various different fault scenarios. If not, the distributed system is altered such as by altering its capacity or its capacity allocations. Performing data placement, testing for fault-tolerance and altering capacity or capacity allocations are performed repetitively, thereby increasing the system's ability to provide the desired performance under the fault scenarios. Preferably, a system and placement are eventually determined that provide the desired performance under the given fault scenarios.