[jimlikeslimes]

I'm not addressing your point on fairness but I've been working on a similar program but instead of taking locks out on the queue table I maintain a consumers position for locked and acknowldeged messages on the consumers table. It makes lots of queries simpler. Here's a simplified schema using SQL Server:

  CREATE TABLE [dbo].[Nodes] (
    [Id]             UNIQUEIDENTIFIER NOT NULL,
    [NetworkId]      UNIQUEIDENTIFIER NOT NULL,    
    [Locked]         INT              NOT NULL,
    [Acknowledged]   INT              NOT NULL,
  );

  CREATE TABLE [dbo].[Messages] (
    [Id]            UNIQUEIDENTIFIER NOT NULL,
    [NetworkId]     UNIQUEIDENTIFIER NOT NULL,
    [NodeId]        UNIQUEIDENTIFIER NOT NULL,    
    [Payload]       NVARCHAR (MAX)   NULL,
    [InsertedOrder] INT DEFAULT (NEXT VALUE FOR dbo.MessageSequence) NOT NULL,
    [TimestampUtc]  DATETIME2 (7)    DEFAULT (sysutcdatetime()) NOT NULL,
  );

  Select * 
  From Nodes With (Rowlock, Holdlock)
  Where NetworkId = @networkId
  And Id = @nodeId

Multi-tenancy is per database.

(edit: simplified sql)