Design of Local-Rule Protocols for Large-Scale File-Sharing Networks
Edward G. Coffman, Andreas Constantinides · 2008
File sharing networks on the Internet are prime candidates for local-rule, distributed network designs. The nodes are file caches and the scale of these networks demands the local-rule paradigms of self-organizing systems for their control. But the generally intractable {\it inverse problem} of cellular automata theory must be faced in these applications as well: Given desired emergent or stable behavior and an initial state $\sigma$, construct a local-rule protocol which yields that behavior when the system is started in $\sigma$. Within the context of a simplified mathematical model of file-sharing systems, we give local-rule solutions to variants of this problem when the desired behavior is seamless (minimum response-time) downloading at minimal total storage cost to the network.