I'm gonna cc infinispan-dev as well, so others can pitch in.
But yeah, good start. I think your dissection of the use cases makes sense, except that I think (a) and (c) are essentially the same; only that in the case of (c) the task ignores any data input. This would raise the question of why would anybody do this, and what purpose does it solve. :-) So yeah, we could support it as a part of (a), but I am less than convinced of its value.
And as for data locality, perhaps this would work: don't define the necessary keys in the Task, but instead provide these when submitting the task. E.g.,
CacheManager.submitTask(task); // task goes everywhere, and receives an input Iterator of all local entries on each node.
CacheManager.submitTask(task, K...); // task goes to certain nodes that contain some or all of K. Receives an input Iterator of all local entries on each node.
WDYT?