Algorithm: Random Crab Updating

Unlike the environmental and habitat components of the model, crabs are updated on average once per hour using an algorithm (described below) that ensures non-sequential updating. Non-sequential updating of individuals in IBMs is essential to prevent spurious patterns and results (Schönfisch and de Roos 1999). A priority queue  (Sedgewick 1992) plays a central role in our algorithm for scheduling the non-sequential updates by facilitating efficient insertions and removals ordered according to update time. There are two cases: no interaction (usually during winter), and interaction between crabs. Under the no interaction case, when a crab is updated all of the crab's state variables are updated and a new update time is generated according to an exponential distribution with mean 1 hr and crabs cycle through the priority queue in a random order so that after 1 and 3 hours, $\approx$ 63% and $\approx$ 95% of the crabs in the estuary will have been updated at least once. Given the rates at which ingestion and egestion occur, the mean update time cannot be increased much beyond 1 hour.

The second case involves crab-crab interactions that occur because a crab encounters conspecifics. Interactions result in even more frequent updates than under no-interactions and also make the above algorithm more complex because increased book-keeping is required to track previously scheduled interactions, enable crabs to be killed and removed from the model estuary without disrupting the inherent ordering of the priority queue.

Algorithmic Details A key assumption made in this algorithm is that over sufficiently small time intervals (minutes) only pairs of crabs interact and display aggression. The algorithm also relies on number of objects and data-structures to function. First, the priority queue stores what we call interaction objects which contain the times at which two crabs are scheduled to interact, pointers or references to the two interacting crabs, and a flag indicating whether or not this interaction should still occur or be canceled. This flag will be discussed further below. In addition to these interaction objects, each crab is stored in an interaction object in which the other crab it interacts with is itself at some future time greater than all other crab-crab interactions it is involved in. The reason for always including such an interaction object is that when a crab is killed, the killed crab is likely involved in other future interactions in the priority queue. As a result, one needs some way to know when a killed crab appears for the last time in the queue, and thus that the computer resources taken up by this crab object can now be freed. By always including a crab's interaction with itself at a time greater than all other interactions, this is easily determined.

Secondly, each individual crab maintains a set of pointers to all the interaction objects that it is potentially involved with. The reason for maintaining this set is because when a crab is updated, all subsequent interactions with other crabs can no longer be assumed to be valid. Thus, this set of pointers is used to change all the flags in the crab's other interaction objects to ``cancel''. As a result, when these interaction objects reach the front of the priority queue they are simply canceled.

The updating algorithm works as follows:

• Remove interaction object from priority queue. If not flagged as canceled, then proceed to update/interact the crabs. Otherwise, free up the interaction object.
• If the crabs are the same, and if the crab has been flagged as killed or dead then free-up the crab's computer resources. If not flagged as killed or dead, then flag any other interaction objects associated with the crab as ``canceled'' and delete the crab's set of pointers to the interaction object. Generate a new update time for the crab and determine if and when in the future it interacts with another crab.
  • If it could interact in the future (See Appendix A.5.3), place both crabs in an interaction object and add to the priority queue. Generate another update time for the crab greater than this (or any other) interaction times and update both crabs' interaction pointer sets.
  • If the crab doesn't interact with another crab, place it back in the priority queue and update its interaction pointer set.
• If the crabs are not the same, then let the two crabs interact and set the interaction objects pointed to by both crabs to ``canceled'' and delete the pointers to these interaction objects.
  • If a crab is killed, flag it as ``killed''. Update the other crab as described above.
  • For all other interaction outcomes, update both crabs singly as described above.