Coordinating adaptations in distributed systems

Distributed applications may use sophisticated runtime adaptation strategies to meet their performance or quality-of-service goals. Coordinating an adaptation that involves multiple processes can require complex communication or synchronization, in addition to communication in the base application. We propose conceptually simple high-level directives and a sophisticated runtime algorithm for coordinating adaptation automatically and transparently in distributed applications. The coordination directives specify when to adapt, in terms of the relative computational progress of each relevant process. The coordination algorithm relies on simple compiler transformations to track the progress of the processes, and performs the adaptive changes locally and asynchronously at each process. Measurements of the runtime overhead of the automatic coordination algorithm for two adaptive applications (a parallel PDE solver and a distributed video tracking code) show that the overhead is less than 1% of execution time for both these codes, even with relatively frequent adaptations, and does not grow significantly with the number of coordinating processes.