We observe a certain random process on a graph "locally", i.e., in theneighborhood of a node, and would like to derive information about"global" properties of the graph. For example, what can we know about agraph based on observing the returns of a random walk to a given node?This can be considered as a discrete version of "Can you hear the shapeof a drum?"Our main result concerns a graph embedded in an orientable surface withgenus g, and a process, consisting of random excitations of edges andrandom balancing around nodes and faces. It is shown that by observingthe process locally in a "small" neighborhood of any node sufficiently(but only polynomially) long, we can determine the genus of the surface.The result depends on the notion of "discrete analytic functions" ongraphs embedded in a surface, and extensions of basic results onanalytic functions to such discrete objects; one of these is the factthat such functions are determined by their values in a "small"neighborhood of any node.This is joint work with Itai Benjamini.

Many important models of stochastic networks exhibit congestion and delay. This implies that the total time a job spends in the system (the "sojourn time") is typically longer than the actual amount of service time needed by the job. The sojourn time is a classical measure of the performance of a queueing system. Recently, various authors have begun to consider more general measures of the delay experienced in a queueing system. One such measure is the "lead time," a dynamic quantity describing the time until expiration of some deadline which the job may have. The initial lead time of a job could be random and different from the service time of the job. In this talk, we will discuss recent results for the GI/GI/1 processor sharing queue when jobs have timing requirements represented as lead times. Our primary tools are fluid model and state space collapse techniques involving a measure valued process that jointly keeps track of residual service times and lead times of individual jobs in the system. The main result is a heavy traffic diffusion approximation for the (appropriately rescaled) measure valued process. This is joint work with Lukasz Kruk.