Briefly, aspects of the subject matter described herein relate to job submission. In aspects, a client (which itself may be a scheduler) sends a request to a scheduler to execute a job. The client may indicate which extensions to a base job submission protocol the client supports. The scheduler may implement a base case protocol and may also implement extensions to the base case. The client and scheduler may communicate information and requests about a job based on extensions both support, if any. The scheduler maintains state information about executing jobs that may include substate information without affecting interoperability with clients that do not recognize substates. A job may be in multiple substates at the same time.