  We investigate the behavior of data structures when the input and operations
are generated by an event graph. This model is inspired by Markov chains. We
are given a fixed graph G, whose nodes are annotated with operations of the
type insert, delete and query. The algorithm responds to the requests as it
encounters them during a (random or adversarial) walk in G. We study the limit
behavior of such a walk and give an efficient algorithm for recognizing which
structures can be generated. We also give a near-optimal algorithm for
successor searching if the event graph is a cycle and the walk is adversarial.
For a random walk, the algorithm becomes optimal.
