wiki:SerpinskyNumbering

 Visit forum
 Forum search "SerpinskyNumbering"
 Discuss "SerpinskyNumbering"

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 2k ranges in a given 2k+1 aligned range get their numbers, the containing 2k+1 range also gets a number

So using binary numbers, every leftmost triangle (i.e. ranges of 2i 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 2n byte range there are 2n+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