Coverings of Finite Sets by Random Covers, with Applications to the HELP Protocol
Ogden, Robert D.
If we choose subsets of a finite set s at random, according to some specified distribution, how many subsets have to be chosen until s is covered? We solve this problem for distributions invariant under permutations of s by a Markov chain model and derive a useful estimate for a sufficient number of subsets to form a cover with a specified probability. These results are applied to the HELP network protocol [GGO] to estimate the number of times the server must send a set of file fragments to clients, not all of them helpful, in order to ensure that all the fragments be shared.
HELP protocol, servers, Markov chain model, Computer Science
Ogden, R. D. (2011). Coverings of finite sets by random covers, with applications to the HELP protocol (Report No. TXSTATE-CS-TR-2011-28). Texas State University-San Marcos, Department of Computer Science.