How to coordinate threads in my use case

This would be easier if you used Future or actors, instead of Threads as a building block. Doing this directly on top of threads can lead to many problems, since you have to take care of details, like queueing incoming messages. Another problem is that I don't get if what you want to solve mirrors what you're asking for - where's the value in executing the same task twice, on 2 different threads? That just feels wrong.

Here's a naive non-blocking implementation to get an idea of what's involved BUT DO NOT DO THIS in real code (really do consider higher-level abstractions):

val queue = new AtomicReference(Queue.empty[Runnable])

def worker() = new Thread(new Runnable {
  @tailrec
  def run() = {
    val currentQueue = queue.get
    if (currentQueue.nonEmpty) {
      val (task, updatedQueue) = currentQueue.dequeue
      try {
        task.run()
      } catch {
        case NonFatal(ex) =>
          ex.printStackTrace()
      }

      // if this fails, then another worker succeeded
      queue.compareAndSet(currentQueue, updatedQueue)
      // process next task in queue
      if (updatedQueue.nonEmpty) run()
    }
  }
})

@tailrec
def submitTask(task: Runnable): Unit =  {
  val currentQueue = queue.get
  val newQueue = currentQueue.enqueue(task)

  if (!queue.compareAndSet(currentQueue, newQueue))
    submitTask(task)
  else if (currentQueue.isEmpty) {
    // because of the CAS above, only 2 workers will be
    // active at the same time
    worker().start()
    worker().start()
  }
}

I would use a variation on Balancing Workloads Across Nodes with Akka 2, except instead of assigning one work item per worker, it assigns the current work item to each worker that requests work until the work item is completed.

It may seem like overkill but this pattern scales very well and is easy to customize. I have two projects in Production using it and there are others. This approach is a "pulling" approach.

A "pushing" approach using actors would require worker actors that only process the last message in their mailbox. The main actor would then forward all messages to all worker actors.

Consider using some Executor, for example Executors.newFixedThreadPool(). It allows:

• Submitting task that will be processed in future;
• Threads that work on tasks won't try completing the same task;
• Future interface returned for each submitted task let you check whether task is completed successfully, still in progress or failed;
• Blocking mechanism you described in 2) can be achieved relying on the fact that Future.get() method blocks until the task is finished/failed to complete;

I think this features cover the behavior requirements you wrote.