Deadlock implementando un protocolo en java

[Instru]

Buen día a todos.

Desde hace tiempo he estado desarrollando lo que se conoce como un Broker del protocolo Mqtt. No es necesario conocer este protocolo.

Mqtt es un protocolo de comunicación entre 2 dispositivos. Su forma de manejar los mensajes es a través de paquetes.
Mi problema se enfoca en 2 paquetes: publish y pubrec.
Un host manda un publish para enviar a otro host un mensaje. Y este otro host debe responder con un pubrec para acusar de recibido el primer publish. Si después de cierto tiempo no se recibe el pubrec se vuelve a enviar el publish.

En java yo implemento esto usando un par de colas concurrentes (ConcurrentLinkedQueue).

Cada vez que se hace una petición de enviar algún mensaje, se encola en la primer cola el publish o los publish que se quieren enviar.
Ahora, en la segunda cola se toma el publish que esta en la cabeza de la primer cola y se envía, pero no se quita de la cabeza de la segunda cola. De esta manera, si no recibimos respuesta, volvemos a enviar el paquete que esta en la cabeza de la segunda cola el cual será el publish que no obtuvo respuesta.

Una vez que llega pubrec, se quita el publish de la segunda cola(aqui en realidad, hay una serie mas de paquetes, pero por simplicidad los omito). Como la segunda cola terminó de trabajar, entonces se toma el siguiente publish de la primer cola.
En pocas palabras la primer cola es literalmente una fila, y la segunda cola es mas bien un buffer de trabajo.

El problema se da cuando 2 hosts quieren enviar un publish casi al mismo tiempo.
Lo que sucede es lo siguiente.
Host1 envía publish y host2 también. Ambos esperan pubrec para poder quitar el publishd e la cabeza. Host1 espera pubrec1 el cual no puede ser enviado porque host2 esta esperando pubrec2 para poder enviar pubrec1.

Por lo tanto los 2 hosts se bloquean intentando enviar publish de manera indefinida sin recibir nunca una respuesta.

Creo que es algo difícil de explicar, pero espero me haya dado a entender.
No se qué hacer para evitar este bloqueo y conserve el orden y todas las propiedades del protocolo mqtt.

Espero alguien pueda ayudarme.

Saludos