Warning: needs renaming, the term Sierpinski number is used for different type of numbers already, absolutely unrelated to the Sierpinsky triangle, but named after the same guy. (Actually, "numbering" and "numbers" mean different things, so may keep it this way.) Possible variant: Młotkovsky numbers.
Jan 2009 : rebranded as M-numbers
Considering MerkleHashes, Video On Demand and P2P streaming, the BitTorrent approach with splitting a file into pieces and passing around bit fields might not be convenient enough. Herewith described a byte range numbering system for infinite streams that might allow efficient representation of possessed/desired pieces in a peer-to-peer swarm.
(BTW, there is a HaveAll/HaveNone proposed BitTorrent extension optimizing the trivial cases.)
Consider an infinite Serpinsky triangle over some infinite byte stream so smallest (base) triangles correspond to bytes, next layer corresponds to 2-byte length 2-byte aligned ranges, next 4-byte, 8-byte etc. The sequential numbering system for triangles/ranges is as follows: 0 is empty set, 1 is first byte, 2 is the second byte, 3 is the first 2-byte range, 4 is the 3rd byte, etc. So,
- ranges are numbered from the beginning, from the bottom (starting with the smallest)
- as two 2^{k} ranges in a given 2^{k+1} aligned range get their numbers, the containing 2^{k+1} range also gets a number
So using binary numbers, every leftmost triangle (i.e. ranges of 2^{i} length starting at the first byte) are numbered 1 (length 1), 11 (length 2), 111 (length 4), 1111 (length 8) etc.
Overhead of using Sierpinsky numbering compared to the simple sequential byte numbering is 1 bit! (as for a 2^{n} byte range there are 2^{n+1} triangles/ranges)
Conclusion
- Esp. if using MerkleHashes instead of .torrent files, Sierpinsky numbering might lower overhead expenses esp. considering distribution of smaller files.
- It also might be more natural for stream broadcasting as the numbering system is infinite compared to the BitTorrent model of fixed-length file distribution (existing workarounds actually do not preserve backward compatibility)
- so, one day in the future we might need it
Note: using MerkleHashes instead of infohashes is not compatible with infinite streams: the hash of the whole stream obviously constantly changes
Attachments
- 180px-Sierpinski_Triangle.svg.png (8.0 KB) - added by victor 6 years ago.
- SerpinskyNumbering.png (72.5 KB) - added by victor 6 years ago.