1. A computer-implemented method comprising: receiving, by a computing system configured to provide a distributed program execution service having a plurality of computing nodes, configuration information indicating a quantity of computing nodes on which to execute an indicated program, wherein executing the indicated program causes a plurality of execution jobs to be executed; selecting, by the configured computing system, the indicated quantity of computing nodes to use as part of a cluster in executing the indicated program in a distributed parallel manner; initiating the executing of the indicated program on the computing nodes of the cluster at a first time by, for each of the multiple computing nodes of the cluster, attempting to initiate execution on the computing node of at least one of the execution jobs; at a second time subsequent to the first time, determining whether a minimum quantity of the computing nodes of the cluster have begun to execute the execution jobs, the minimum quantity being less than the indicated quantity; and if it is determined at the second time that the minimum quantity of the computing nodes of the cluster have not begun to execute the execution jobs, initiating termination of the executing of the indicated program on the computing nodes of the cluster without completing the executing of the indicated program, and otherwise continuing the executing of the indicated program until the executing of the indicated program is completed.