This is a hard problem in distributed systems and requires centralizing locks and doing some up-front work for scheduling so no delays will be experienced. My interviewer amazingly thought SQS was the right approach. I was just amazed that he did not really understand SQS, a very mature and basic AWS service...on any level really. He then seemed to backpedal and weaken his requirements for "only-once" and "synchronous"...but that was just him moving the goalposts after the fact.