I think the best way would be to target a random 500 machines for the deployment, then after it has been going for a while and deployed to many machines, then stop the action, see how many got it, then deploy to others to fill in the gaps.
There might be some other creative options, but this is kind of unusual.
It might be possible to orchestrate something like this with server automation.