Обработка зависших задач

Как кто решает следующую задачу. Она про CAP-теорему, как мне кажется.

Есть n воркеров. Есть k задач, которые представляют собой записи в БД со статусами (NEW, CHECKING, COMPLETE, ERROR). Изначально все задачи в состоянии NEW. Воркер вычитывает статус из БД и ставит задачу в CHECKING транзакционно. Если воркер успешно обрабатывает задачу, то выставляет её в COMPLETE. Если воркер обрабатывает с ошибкой задачу, то ставит её в ERROR. Но если воркер отваливается, то задача остаётся висеть в CHECKING. Эту проблему мы решаем ещё 1 воркером, который запускается раз в 15 минут и выставвляется для всех задач, у которых не было обновления более 15 минут в ERROR. Но в таком случае задержка оказывается очень большой. Каким образом можно ещё решать такую проблему?