I'm having a really hard time finding a solution to a practical programming problem, and I think raw CS might have an answer.
The requirement is for a familiar message queue for which there are multiple message Generators and multiple message Consumers. Generators enqueue messages into a queue within the scope of an transaction. Consumers dequeue messages within the scope of a transaction, and process the message successfully, removing it from the queue, or fail and roll back the transaction in which case the message remains on the queue. The message may be left on the queue by the Consumer in an altered state - decrementing a retry-count, for example.
Adding to this the concept of a Sequence or Conversation - a partial ordering within the set of all messages in the queue. Messages which are part of a Sequence are to be consumed in-order. Sequences are unordered amongst Sequences.
Generators do not block other Generators unless the messages being enqueued are for the same Sequence. Generators never block Consumers. Consumers never block Generators. And Consumers never block other Consumers. That is, Enqueue() may block, Dequeue() never blocks. Generators Enqueue a message exactly once. Consumers successfully process each message exactly once.
It'd be nice if the implementation doesn't leave too much trash data around, but as long as old data can eventually be trimmed, that's fine.
It seems like this scenario should be possible, yet I cannot find or design correct rules on a common platform. SQL Service Broker might match all of these criteria, but if it does, how does it?
Is such a protocol provably impossible? If not, how might it be done/what properties must the underlying storage platform have to support it?