alloy

Forcing InProgress state machines to always resolve


I am trying to model executions of concurrent AWS Lambda functions to look for bugs around timing. In my model, once a Lambda is triggered, it should always end up in either a Complete or Failed state. The problem is, I can't figure out how to tell Alloy to throw out any state sequence where Lambdas are still InProgress in the final state.

Here is what I have. In the actual model, there would be side effects of the state transitions which I would want to make assertions about. Basically "once every lambda is complete or failed, X should be impossible".

abstract sig State {}
sig InProgress, Complete, Failed extends State {}

var sig Lambda {
   var state: one State,
} {
  this in Lambda'
}

pred complete[l:Lambda] {
   l.state' in Complete + Failed
}

pred can_step[l:Lambda] {
  l.state = InProgress 
}

pred wait[l:Lambda] {
 l.state' = l.state
}

pred step_lambdas[] {
  all l: Lambda {
     can_step[l] implies (complete[l] or wait[l]) else wait[l]
  }
  lone l: Lambda | complete[l] // only let one lambda complete at at time
}

pred trigger_lambda[] {
  one l: Lambda' | Lambda' = Lambda + l' and l.state' = InProgress
}

pred do_nothing[] {
  Lambda != none
  Lambda = Lambda'
}

fact {
  Lambda = none
  always trigger_lambda or do_nothing
  always step_lambdas
}

check {
  eventually {
    some Lambda
    no l: Lambda | can_step[l] 
  }
}

Update #1: I tried changing the check statement to the below. I believe it should show me a violation with t0, t1, t2 where at t2 there is a Lambda with state = Error. Instead, it shows me a violation with t0, t1 where at t1 there is a Lambda with state = InProgress. I don't see how this violates the check.

...

check {
  some Lambda
  (all l:Lambda |  not can_step[l]) implies all l:Lambda | l.state = Complete
}

Solution


I figured it out. I need to express the check in the form "All lambdas must always be able to step or be in a completed state."

check {
  always all l:Lambda | can_step[l] or l.state in Complete
}

Complete model which finds a counterexample where a lambda ends in Failed state.

abstract sig State {}
sig InProgress, Complete, Failed extends State {}

var sig Lambda {
   var state: one State,
} {
  this in Lambda'
}

pred complete[l:Lambda] {
   l.state' in Complete + Failed
}

pred can_step[l:Lambda] {
  l.state = InProgress
}

pred wait[l:Lambda] {
 l.state' = l.state
}

pred step_lambdas[] {
  all l: Lambda {
     can_step[l] implies (complete[l] or wait[l]) else wait[l]
  }
  lone l: Lambda | complete[l] // only let one lambda complete at at time
}

pred trigger_lambda[] {
  one l: Lambda' | Lambda' = Lambda + l' and l.state' = InProgress
}

pred do_nothing[] {
  Lambda != none
  Lambda = Lambda'
}

fact {
  Lambda = none
  always trigger_lambda or do_nothing
  always step_lambdas
}

check {
  always all l:Lambda | can_step[l] or l.state in Complete
}