Sharpness a Tight Condition for Scalability

A distributed system is scalable if the rate at which it completes its computation and communication tasks does not depend on its size. As an example, the scalability of a peer-to-peer application that transmits data among a large group depends on the topology and the synchronization implemented between the peers. This paper describes a model designed to shed light on the conditions that enable scalability. Formally, the authors model here a collection of tasks, each requiring a random amount of time, which are related by precedence constraints.