Scalable, parallel (i.e., concurrent) processing of messages is provided from a message queue, while at the same time enforcing sequencing within a stream. Dependencies among messages can therefore be respected. The criteria for determining which messages form a stream are not required to be known to the message dispatcher, which receives a stream name and determines whether another message in that named stream is already being processed. If so, the dispatcher determines whether the invoker should wait temporarily, or should be given a different message that was previously blocked and has now become available for processing, or should be instructed to retrieve a different message from the message queue.