find all permutations for the first k letters and distribute them to different machines to find the remaining l letters. If you choose k reasonably you won't need to safe state, just finish l.