The combination of service-oriented applications, with their run-time service binding, and mobile ad hoc networks, with their transient communication topologies, brings a new level of complex dynamism to the structure and behavior of software systems. This complexity challenges our ability to understand the dependence relationships among system components when performing analyses such as fault localization and impact analysis. Current methods of dynamic dependence discovery, developed for use in fixed networks, assume that dependencies change slowly. Moreover, they require relatively long monitoring periods as well as substantial memory and communication resources, which are impractical in the mobile ad hoc network environment. We describe a new method, designed specifically for this environment, that allows the engineer to trade accuracy against cost, yielding dynamic snapshots of dependence relationships. We evaluate our method in terms of the accuracy of the discovered dependencies. © 2013 IFIP.