Detta dokument undersöker spridningen av flera delar av information i stora nätverk där användare kontaktar varandra på ett slumpmässigt okoordinerat sätt, och användare laddar upp en bit per tidsenhet. Den underliggande motivationen är utformningen och analysen av styckeurval protokoll för peer-to-peer nätverk som sprider filer genom att dela dem i bitar. Vi undersöker först ensidiga protokoll, där partiurval baseras på tillstånden hos antingen sändaren eller mottagaren. Vi visar att ett sådant protokoll som endast bygger på pushs, eller alternativt bara pulls, kommer att vara ineffektivt när det gäller att sprida alla bitar till alla användare. Vi föreslår en hybrid ensidig bit urval protokoll -INTERLEAVE - och visa att genom att använda både pushes och drar den sprider k bitar från en enda källa till n-användare i 10 (k + log n) tid, samtidigt som du följer den begränsning som varje användare kan ladda upp som mest en bit i en enhet av tid. Ett optimalt, orealistiskt centraliserat protokoll skulle ta k + log 2 n tid i denna inställning. Dessutom är effektiv spridning också möjligt om källan implementerar framåt radering kodning, och användare skjuta de senast släppta kodade bitar (men dra inte). Vi undersöker även tvåsidiga protokoll där partiurval baseras på både trasmittorns och mottagarens tillstånd. Vi visar att det är möjligt att sprida n bitar till n användare i n + O (log n) tid, med början från ett initialtillstånd där varje användare har en unik bit. 1 Användningen av fildelning för multihopöverföringar liknar den välkända tekniken för cut-through routing, se [13] 2 I BitTorrent till exempel, detta beslut fattas av varje användare endast på grundval av information från sina grannar. Varje peer opinionsundersökningar sina grannar för sina verk samlingar, och sedan laddar ner den lokalt sällsyntaste biten, dvs.. Det verk som har den lägsta representationen i kamraternas grannar.
Sanghavi m.fl. Ref överväga problemet med att sända flera paket i P2P-nätverk, och föreslå en decentraliserad paket utbyte algoritm baserad på pushes och drag som har en nära-optimal prestanda.
Gossiping with Multiple Messages
{'venue': 'IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications', 'journal': 'IEEE INFOCOM 2007 - 26th IEEE International Conference on Computer Communications', 'mag_field_of_study': ['Computer Science', 'Mathematics']}