Should we implement http://nick-lab.gs.washington.edu/java/jdk1.5b/api/java/util/concurrent/Cancellable.html ?
If you make a second patch, remove the '-' in below since you went and edited javadoc
+ * @param cs - the completion service to use for submitting
+ * @param rl - the region locations
+ * @param min - the id of the first replica, inclusive
+ * @param max - the id of the last replica, inclusive.
What does this mean client-side?
+ * This means as well that it can be used for a small set of tasks only.
Scanned patch. Looks great.