The mailbox problem

We propose and solve a synchronization problem called the mailbox problem, motivated by a particular type of interaction between a processor and an external device or between two threads. In this problem, a postman delivers letters to the mailbox of a home owner and uses a flag to signal a non-empty mailbox. The owner must remove all letters delivered to the mailbox and should not walk to the mailbox if it is empty. We present algorithms and an impossibility result for this problem.