Techniques for implementing software licensing in a massive parallel processing environment on the basis of the actual use of licensed software instances are disclosed. In one embodiment, rather than using a license server or a node-locked license strategy, each use of a licensed software instance is monitored and correlated with a token. A store of tokens is maintained within the licensing system and a token is consumed after each instance successfully executes. Further, a disclosed embodiment also allows jobs that execute multiple software instances to complete execution, even if an adequate number of tokens does not exist for each remaining software instance. Once the license tokens are repurchased and replenished, any overage consumed from previous job executions may be reconciled. In this way, token-based licensing can be adapted to large scale computing environments that execute jobs of large and unpredictable sizes, while the cancellation of executing jobs may be avoided.