I think it would help to clarify which collections.deque methods are thread-safe:

http://docs.python.org/dev/library/collections.html?highlight=deque#collections.deque

Currently, the documentation says that "Deques support thread-safe, memory efficient appends and pops from either side...," but it isn't obvious if this is meant to apply to all methods, or just the methods named append*() and pop*().

For example, is rotate() thread-safe?  The illustration given of d.appendleft(d.pop()) seems like it could be interleaved.