Minor Description
initialize() can receive a null parameter for messages (at least that's what EdgeListVertex does). We should avoid that and pass an empty Iterable instead. That should be cheap for us inside of the InputFormat, just passing a static immutable empty list.
setMessages(Iterable<M>) should be changed to putMessages(Iterable<M>). the set prefix suggests an assignment, while setMessages is used to transfer the messages to the internal datastructure the user is responsible for. putMessages() should clarify this.