Coverings of Finite Sets by Random Covers, with Applications to the HELP Protocol

Date

2011-01-08

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.

Rights

Rights Holder

Rights License

Rights URI