Peer-to-Peer-Netzwerke: Algorithmen und Methoden

nur zwei Typen von Variablen betrachtet werden:
    1. Diskrete Zufallsvariablen: X : [7 -f .f7' mit endlicher oder abzahlbarer Menge [7', wie zum Beispiel [7' = N
    2. Kontinuierliche Zufallsvariablen X : [ -* R. Hier kann man die Wahrscheinlichkeit durch eine Dichtefunktion f : JR - R beschreiben, wobei

    Hierbei ist Fx (y) = Pr[X < y] die so genannte kumulierte Wahrscheinlich- keitsfunktion oder die Wahrscheinlichkeitsverteilung von X.
    Der Erwartungswert einer kontinuierlichen Zufallsvariablen, gegeben durch die Dichtefunktion f, ist:

    Fur diskrete Zufallsvariablen ist der Erwartungswert definiert durch

    wobei mit x E X die Menge aller diskreten Werte der Zufallsvariablen aufgezahlt wird. Die Varianz ist definiert als

    Es gilt

Markov, Tschebyscheff and Chernoff
    Fur die Abschatzung von Zufallsvariablen kennt man die folgenden Ungleichungen:
Theorem A.1 (Markov-Ungleichung).
    Pr[X > c E[X]] < . c
    Theorem A.2 (Tschebyscheff-Ungleichung). Fur alle k > 0 gilt
    Pr[IX - p > k] < V(X) k2
    Sind die Variablen unabhangig, so Iasst sich folgende scharfere Abschatzung verwenden. Ein Bernoulli-Experiment hat als Ergebnisraum {0, 1}. Zwei Zufallsexpe- rimente sind unabhangig, wenn

    Entsprechend gilt fur das Ergebnis mehrerer Zufallsvariablen Xi die Unabhangigkeit, wenn

    fur alle Moglichkeiten von yi.

    Des Weiteren gilt fiir 0 < b < 1, dass

B

Eingetragene Warenzeichen
    Sun TM, Sun MicrosystemsTM, Java TM, JXTATM, and SunOSTMsind Warenzeichen oder eingetragene Warenzeichen von Sun Microsystems, Inc. in den Vereinigten Staaten and in anderen Landern.
    LinuxTMist ein eingetragenes Warenzeichen von Linus Torvalds.
    MacTM- Operating System software - ist ein eingetragenes Warenzeichen von Apple Computer, Inc.
    MicrosoftTM, Windows TM sind Warenzeichen oder eingetragene Warenzeichen von Microsoft Corporation in den Vereinigten Staaten and in anderen Landern.
    Google and Google-Mail sind Warenzeichen oder eingetragene Warenzeichen von Google Inc. in den Vereinigten Staaten and in anderen Landern.
    CacheLogic and Streamsight sind eingetragene Warenzeichen von CacheLogic Limited.
    BitTorrent ist ein Warenzeichen von BitTorrent Inc.
    NapsterTM ist ein eingetragenes Warenzeichen von Napster, LLC.
    Der Name Kazaa and Kazaa verwandte Produkte sind Warenzeichen von Sharman Networks Limited.
    Skype TM ist ein Warenzeichen von Skype Technologies SA.
    Andere genannte Produktmarken sind eingetragene Warenzeichen der jeweiligen Inhaber.

Literaturverzeichnis
    1. Sullivan, J.: GNU General Public License. http://www.gnu.org/copyleft/gpl.html (2006)
    2. CollabNet: JXTA - company spotlight archive. http://www.jxta.org/companies/ companyarchive.html (2006)
    3. Baset, S.A., Schulzrinne, H.: An analysis of the skype peer-to-peer internel telephony protocol. http://arxiv.org/abs/cs/0412017 (2004)
    4. Clarke, I., Sandberg, 0., Wiley, B., Hong, T.W.: Freenet: A distributed anonymous information storage and retrieval system. In: International Workshop on Design Issues in Anonymity and Unobservability. (2000) 311-320
    5. Orwant, J.: What's on Freenet? http://www.openp2p.com/pub/a/p2p/2000/11/21/ freenetcontent.html (2001)
    6. Cachelogic: P2P in 2005. http://www.cachelogic.com (2005)
    7. Clip2: The Gnutella protocol specification v0.4. http://www9.limewire.com/developer/ gnutella_protocol_0.4.pdf (2001)
    8. Ratnasamy, S., Francis, P., Handley, M., Karp, R., Shenker, S.: A scalable contentaddressable network. In: Computer Communication Review. Volume 31., Dept. of Elec. Eng. and Comp. Sci., University of California, Berkeley (2001) 161-172
    9. Karger, D., Lehman, E., Leighton, T., Levine, M., Lewin, D., Panigrahy, R.: Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, El Paso, Texas (1997) 654-663
    10. Stoica, I., Morris, R., Karger, D., Kaashoek, F., Balakrishnan, H.: Chord: A scalable Peer-To-Peer lookup service for internet applications. In Guerin, R., ed.: Proceedings of the ACM SIGCOMM 2001 Conference (SIGCOMM-0 1). Volume 31, 4 of Computer Communication Review., New York, ACM Press (2001) 149-160
    11. Rowstron, A., Druschel, P.: Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. Lecture Notes in Computer Science, In Proc. of the International Conference on Distributed Systems Platforms (IFIP/ACM), 2218 (2001) 329-350
    12. Hildrum, K., Kubiatowicz, J.D., Rao,