[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Specifying a stopping condition



Am Sonntag, 16. Dezember 2018 16:45:31 UTC+1 schrieb nic...@xxxxxxxxx:
> Am Sonntag, 16. Dezember 2018 02:09:31 UTC+1 schrieb Leslie Lamport:
> > If, at the end of error trace, it says something like "back to state 17", then the error trace is an infinite trace that ends by infinitely repeating the sequence of states from state number 17 through the last displayed state.
> > 
> > 
> > Leslie 
> > 
> > 
> > On Saturday, December 15, 2018 at 4:36:27 PM UTC-8, nickkell at gmail.com wrote:Hello all!
> > 
> > 
> > 
> > I've been working on a spec for a print queue, and ideally it should stop when all the items to be printed are either "printed" or "failed". Multiple "worker" applications are competing to be the next to print for any given printer so have to acquire a lock. I also wanted to model what happens when the workers crash and restart. This is the end of the spec (for brevity):
> > 
> > 
> > 
> > RetrieveNextPrintjob == \E worker \in WORKER, printer \in PRINTER : GetNextForPrinting(worker, printer)
> > 
> > DoPrint == \E worker \in WORKER, printjob \in PRINTJOB : WorkerProcessPrintJob(worker, printjob)
> > 
> > UpdateStatus == \E worker \in WORKER, printjob \in PRINTJOB : HubReceivedPrintJobMessage(worker, printjob) 
> > 
> > Advance == 
> > 
> >     \/ RetrieveNextPrintjob    
> > 
> >     \/ DoPrint
> > 
> >     \/ UpdateStatus
> > 
> > 
> > 
> > Failure == \E worker \in WORKER : WorkerRestart(worker)
> > 
> > 
> > 
> > Next ==
> > 
> >     \/ Advance
> > 
> >     \/ Failure    
> > 
> >     
> > 
> > PQ == Init /\ [][Next]_vars
> > 
> > 
> > 
> > AllPrintJobsFinished == \A printjob \in PRINTJOB : printjobState[printjob] \in {"printed","failed"}
> > 
> > 
> > 
> > Spec == PQ /\ SF_vars(Advance)
> > 
> > 
> > 
> > Liveness == <>[]AllPrintJobsFinished
> > 
> > 
> > 
> > 
> > 
> > The model checker seems to report that after a WorkerRestart, it goes back to a previous state. Does this mean it will repeatedly flip back and forth without terminating?
> 
> Thanks for your reply. So actions "Advance" and "Failure" will both be enabled, and it can always choose to fail, without advancing towards termination. Should I instead specify that action Advance will always be enabled when AllPrintJobsFinished is false? If so, then how?

I have a solution, but I don't know if it's correct or just a workaround. I've introduced a counter that's incremented by the WorkerRestart action, which (along with an upper limit as a State Constraint) prevents an infinite cycle of states. 
Feel free to tell me if it's silly, otherwise I'll remain blissful in my ignorance :)