Just a quick comment on the patch: in as_completed(), if the future is cancelled or finished, control is yielded back to the caller with the condition's lock held.
As a general rule, libraries should not yield control to the caller with a lock held, because depending on what the client does, this can lead to a deadlock. 
For example, Future.__repr__() acquires the future's lock: since the current implementation uses a reentrant lock, it won't cause a deadlock if called from the same thread, but it could deadlock e.g. if another thread called a similar method which acquires this lock.
Also, more generally, when you hold an object's lock it's to make sure that it's always seen in a consistent state, and yielding control to the user means that it can potentially see it in an inconsistent state.

See e.g. the excellent "Java Concurrency in Practice", or "Effective Java" for more details.