Surviable monitoring in dynamic networks

We present a monitoring system for a dynamic network, in which a set of domain nodes shares the responsibility for producing and storing monitoring information about a set of visitors. This information is stored persistently when the set of domain nodes grows and shrinks. Such a system can be used to store traffic or other logs for auditing, or can be used as a subroutine for many applications to allow significant increases in functionality and reliability. The features of our system include authenticating visitors, monitoring their traffic through the domain, and storing this information in a persistent, efficient, and searchable manner. The storage process is O(log n)-competitive in the number of network messages with respect to an optimal offline algorithm; we show that this is as good as any online algorithm can achieve, and significantly better than many commonly used strategies for distributed load balancing.