Scheduling, Percolation, and the Worm Order

We show that in any submodular system there is a maximal chain
that is minimal, in a very strong sense, among all paths from 0 to 1.
The consequence is a set of general conditions under which parallel
scheduling can be done without backward steps.

  Among the applications are a fast algorithm for scheduling
multiple processes without overusing a resource; a theorem about
searching for a lost child in a forest; and a closed-form expression
for the probability of escaping from the origin in a form of
coordinate percolation.

  Joint work in part with Graham Brightwell (LSE) and in part
with Lizz Moseman (USMA).