Start Over After Pre‐Empt (SOAP) Protocol

ABSTRACT Consider a job that normally requires units of time to complete. A higher authority comes and interrupts the service. The inter‐arrival times of the interrupts are , which are the actual available service times to work on the job. Thus, if the first available service time is larger than , the job gets completed, and the remaining service time is the first available service time for the next job. If not, the previous service is lost and service on the job starts from scratch using the next available service time. As before, if , the job gets completed and the remaining service time is the first available service time for the next job. If not, the service is lost, and is the available service time for the job. And so on. Let be the time to complete the job. This is called the start over after pre‐empt (SOAP) protocol. An example of such interrupts is power outages. After a power outage interrupt the partial service on a job running on a computer is lost and service on the job has to start again. We study properties of and , the time to complete two jobs normally requiring times , and give some guidance whether when . We obtain the asymptotic distribution of a stochastic process based on which has interesting independent increments of a new type. My frustrations standing in a queue in India, where a supervisor interrupts and the service on my job has to start again, were my inspiration for the protocol named here as SOAP. A careful referee pointed out that the SOAP protocol is not new in the queues literature. It goes by the name RESTART and has variants called RESUME and REPLACE.