Modeling random failures in a connected graph in Alloy

Question

Is it possible to model random failures in Alloy?

For instance, I currently have a connected graph that is passing data at various time steps to its neighbors. What I am trying to do is figure out some method for allowing the model to randomly kill links, and in doing so, still manage to fulfill its goal (of ensuring that all nodes have had their data state set to On).

open util/ordering[Time]

enum Datum{Off, On} // A simple representation of the state of each node

sig Time{state:Node->one Datum} // at each time we have a network state

abstract sig Node{
  neighbours:set Node 
}
fact { 
  neighbours = ~neighbours   -- symmetric
  no iden & neighbours          -- no loops
  all n : Node | Node in n.*neighbours -- connected
  --  all n : Node | (Node - n) in n.neighbours -- comp. connected
}
fact start{// At the start exactly one node has the datum
  one n:Node|first.state[n]=On
}

fact simple_change{ // in one time step all neighbours of On nodes become on
  all t:Time-last |
    let t_on = t.state.On |
    next[t].state.On = t_on+t_on.neighbours
}

run {} for 5 Time, 10 Node

The software I'm attempting to model deals in uncertainty. Basically, links between nodes can fail, and the software reroutes along another path. What I'd like to try to do in Alloy is to have some facility for links to 'die' at certain timesteps (preferably randomly). In the top-most fact, I have the capability for the graph to be completely connected, so its possible that, if a link dies, another can possibly pick up the slack (as the simple_change switches the state of the Datum to be On for all connected neighbors).

Edit:

So, I did as was suggested and ran into the following error: Type Error
I am confused, as I thought neighbours and Node were still sets?

Here is my updated code:

open util/ordering[Time]
open util/relation

enum Datum{Off, On} // A simple representation of the state of each node

sig Time{
  neighbours : Node->Node,
  state:Node->one Datum         // at each time we have a network state
}{
  symmetric[neighbours, Node]
}
abstract sig Node{
  neighbours:set Node
}

fact { 
  neighbours = ~neighbours   -- symmetric
  no iden & neighbours          -- no loops
--  all n : Node | (Node - n) in n.neighbours -- comp. connected
  all n : Node | Node in n.*neighbours -- connected
}

// At the start exactly one node has the datum
fact start{
  one n:Node|first.state[n]=On
}

// in one time step all neighbours of On nodes become on
fact simple_change{ 
  all t:Time-last |
    let t_on = t.state.On |
    next[t].state.On = t_on+t_on.neighbours

  all t:Time-last | next[t].neighbours in t.neighbours
  all t:Time-last | lone t.neighbours - next[t].neighbours
}

run {} for 10 Time, 3 Node

user1513683 user1513683 · Accepted Answer · 2012-12-05T06:10:32

Move the definition of neighbours into Time:

sig Time {neighbours : Node->Node, ....}

You will need to re-express the facts about symmetry etc of neighbours relative to each time point. This is most easily done by doing it in the invariant part of the Time signature:

sig Time {
  neighbours : Node->Node,
  ...
}{
  symmetric[neighbours, Node],
  ....
}

(I do recommend the use of open util/relation to load useful definitions such as symmetric.)

Then the time step simple_change can be complicated by adding in a fact such as

next[t].neighbours in t.neighbours

which can throw away arbitrarily many arcs.

If you want to restrict how many arcs are thrown away in each step you can add a further fact such as

lone t.neighbours - next[t].neighbours

which restricts disposal to at most one arc.

Modeling random failures in a connected graph in Alloy

1 Answers