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

Simple item page
dc.contributor.authorOgden, Robert D.
dc.date.accessioned2011-02-08T10:03:26Z
dc.date.available2012-02-24T10:03:39Z
dc.date.issued2011-01
dc.description.abstractIf 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.
dc.description.departmentComputer Science
dc.formatText
dc.format.extent9 pages
dc.format.medium1 file (.pdf)
dc.identifier.citationOgden, 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.
dc.identifier.urihttps://hdl.handle.net/10877/2593
dc.language.isoen
dc.subjectHELP protocol
dc.subjectservers
dc.subjectMarkov chain model
dc.subjectComputer Science
dc.titleCoverings of Finite Sets by Random Covers, with Applications to the HELP Protocol
dc.typeReport

Files

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
fulltext.pdf
Size:
126.53 KB
Format:
Adobe Portable Document Format
Download

Collections

College of Science and Engineering