Stabilizing pipelines for streaming applications

摘要

In this paper, we study a compositional approach to designing a class of stabilizing distributed systems. We show that the linear pipelined composition of a number of stabilizing modules is inherently stabilizing, and is a useful method of constructing scalable stabilizing solutions for streaming applications that are on the rise in peer-to-peer and sensor networks. We present the correctness proof and complexity analysis of the composition for a linear pipeline. Subsequently, we generalize the pipelined composition to alternative, concurrent, and repetitive versions, investigate the stabilization properties of these versions, and present a set of conditions under which these extended constructions retain their stabilization properties.