Coverings of Finite Sets by Random Covers, with Applications to the HELP Protocol
Date
2011-01
Authors
Ogden, Robert D.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
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.
Description
Keywords
HELP protocol, servers, Markov chain model, Computer Science
Citation
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.