P2P P2P 2005 Past 2 Present Questions Comments

P2P P2P 2005 Past 2 Present Questions Comments www.phwiki.com

P2P P2P 2005 Past 2 Present Questions Comments

Gardiner, Bryan, Contributing Reporter/Writer has reference to this Academic Journal, PHwiki organized this Journal P2P P2P 2005 Distributed Computing Group Roger Wattenhofer Past 2 Present My Research Distributed Computing Theory Wireless Networking (Ad Hoc, Sensor) Distributed Systems P2P Disclaimer: I’m a P2P ignorant giving a P2P talk P2P vs. Ad Hoc/Sensor Networking Often considered to be “similar” Without infrastructure, without servers, etc. Routing is essential Both feature some sort of topology control (“What are the neighbors”) Major differences Internet vs. wireless (interference, MAC layer, etc.) Graph theory vs. geometry ( really!) Churn vs. mobility Completely different applications

Pennsylvania State University-Penn State Dubois PA www.phwiki.com

This Particular University is Related to this Particular Journal

P2P vs. Distributed Computing/Systems Let’s first try to “prove” Lemma 1 in addition to then convince you about Corollary 2 Ignorant’s Lemma 1: P2P research is the child of successful file sharing applications a la Napster in addition to the distributed computing/systems community Ignorant’s Corollary 2: A child should learn from his/her parents Overview Introduction Past What is the first P2P paper/system Really Present The Four P2P Evangelists If you read your average P2P paper, there are (almost) always four papers cited who “invented” efficient P2P in 2001: These papers are somewhat similar, with the exception of CAN (which is not really efficient) So what’s the „Dead Sea Scrolls of P2P” Chord CAN Pastry Tapestry

“Dead Sea Scrolls of P2P” „Accessing Nearby Copies of Replicated Objects in a Distributed Environment“, by Greg Plaxton, Rajmohan Rajaraman, in addition to Andrea Richa, at SPAA 1997. Basically, the paper proposes an efficient search routine (similar to the evangelist papers). In particular search, insert, delete, storage costs are all logarithmic, the base of the logarithm is a parameter. However, it‘s a theory paper, so that alone would be too simple So the paper takes into account latency; in particular it is assumed that nodes are living in a metric, in addition to that the graph is of „bounded growth“ (meaning that node densities do not change abruptly). Genealogy of P2P Chord CAN Pastry Tapestry 2001 Napster 1997 2002 Kademlia P-Grid Viceroy SkipGraph SkipNet 2003 Plaxton et al. Koorde 1998 1999 2000 Gnutella Kazaa Gnutella-2 eDonkey BitTorrent Skype Steam WWW, POTS, etc. PS3 The parents of Plaxton et al. Overview Introduction Past What is the first P2P paper/system Really Present

Consistent Hashing “Consistent hashing in addition to r in addition to om trees: Distributed caching protocols as long as relieving hot spots on the World Wide Web.” David Karger, Eric Lehman, Tom Leighton, Matthew Levine, Daniel Lewin in addition to Rina Panigrahy, at STOC 1997. Big difference: still a client/server paradigm. Locating Shared Objects “Sparse Partitions”. Baruch Awerbuch in addition to David Peleg, at FOCS 1990. “Concurrent Online Tracking of Mobile Users”. Baruch Awerbuch in addition to David Peleg, at SIGCOMM 1991. “Locating Nearby Copies of Replicated Internet Servers”. James Guyton in addition to Michael Schwartz, at SIGCOMM 1995. “A Model as long as Worldwide Tracking of Distributed Objects”. Marteen van Steen, Franz Hauck, Andrew Tanenbaum, at TINA 1996. Maintaining a distributed directory. Compact Routing “A trade-off between space in addition to efficiency as long as routing tables”. David Peleg in addition to Eli Upfal, at STOC 1988. Trade-off routing table memory space vs. stretch (quality of routes) Name-independent vs. labeled routing Name-independent: the node names are fixed (like in a regular network) Labeled: a designer can choose names (P2P) In particular interesting if latency does matter.

Hypercubic Topologies In my lecture Distributed Computing I teach six topologies: Hypercube Butterfly / Benes Network DeBruijn Graph Skip List Pancake Graph Cube-Connected-Cycles Chord Kademlia Viceroy SkipGraph SkipNet Plaxton et al. Koorde Your-name-here Kuhn et al. Overview Introduction Past Present Dynamic systems & mobility Fault-tolerance (crash failures) Security (Byzantine failures) Selfish agents & computational economy Simple in addition to implementable algorithms Local algorithms Geometry, metrics, bounded growth, etc. Applications current hot topics in distributed computing Dynamic Peer-to-Peer Systems Properties compared to centralized client/server approach Availability, Reliability, Efficiency Peers may join in addition to leave the network at any time! However, P2P systems are composed of unreliable desktop machines under control of individual users “A Self-Repairing Peer-to-Peer System Resilient to Dynamic Adversarial Churn”. Fabian Kuhn, Stefan Schmid, Roger Wattenhofer, at IPTPS 2005.

Churn (permanent joins in addition to leaves) How to maintain desirable properties such as Connectivity, Network diameter, Peer degree Motivation Why permanent churn Saroiu et al.: „A Measurement Study of P2P File Sharing Systems“ Peers join system as long as one hour on average Hundreds of changes per second with millions of peers in system! Why adversarial (worst-case) churn E.g., a crawler takes down neighboring machines rather than r in addition to omly chosen peers! The Adversary Model worst-case faults with an adversary ADV(J,L,) ADV(J,L,) has complete visibility of the entire state of the system May add at most J in addition to remove at most L peers in any time period of length Note: Adversary is not Byzantine!

Synchronous Model Our system is synchronous, i.e., our algorithms run in rounds. One round: receive messages, local computation, send messages However: Real distributed systems are asynchronous! But: Notion of time necessary to bound the adversary A First Approach What if number of peers is not 2i How to prevent degeneration Where to store data Idea: Simulate the hypercube Fault-tolerant hypercube Simulated Hypercube System Basic components: Simulation: Each node consists of several peers Route peers to sparse areas Adapt dimension Token distribution In as long as mation aggregation

Example: In as long as mation Aggregation Algorithm: Count peers in every sub-cube by exchange with corresponding neighbor Correct number after d steps! Results All our algorithms (token distribution in addition to data aggregation) consistently run in the background. We can tolerate an adversary who can insert/delete O(log n) peers per maximum message delay. Our system is never fully repaired, but always fully functional. In detail, we have in spite of ADV(O(log n),O(log n),1): always at least one peer per node, at most O(log n) peers per node, network diameter O(log n), peer degree O(log n). Overview Introduction Past Present Dynamic systems & mobility Fault-tolerance (crash failures) Security (Byzantine failures) Selfish agents & computational economy Simple in addition to implementable algorithms Local algorithms Geometry, metrics, bounded growth, etc. Applications

Gardiner, Bryan Wired News Contributing Reporter/Writer www.phwiki.com

Byzantine Failures If adversary controls more in addition to more corrupted nodes in addition to then crashes all of them at the same time (“sleepers”), we st in addition to no chance. “Robust Distributed Name Service”. Baruch Awerbuch in addition to Christian Scheideler, at IPTPS 2004. Idea: Assume that the Byzantine peers are the minority. If the corrupted nodes are the majority in a specific part of the system, they can be detected (because of their unusual high density). Overview Introduction Past Present Dynamic systems & mobility Fault-tolerance (crash failures) Security (Byzantine failures) Selfish agents & computational economy Simple in addition to implementable algorithms Local algorithms Geometry, metrics, bounded growth, etc. Applications Selfish Agents Freeloading How to generalize BitTorrent’s “tit4tat” mechanism But also: In unstructured P2P systems: Who should I connect to I want to be highly connected since this improves my searches I want to have few neighbors only ( as long as ward too many searches) Hypercubic networks probably are a “socially efficient” solution, however, if every node acts selfishly, do we end up with a hypercubic network! “On a network creation game”. Alex Fabrikant, Ankur Luthra, Elitza Maneva, Christos H. Papadimitriou, Scott Shenker, at PODC 2003

Overview Introduction Past Present Dynamic systems & mobility Fault-tolerance (crash failures) Security (Byzantine failures) Selfish agents & computational economy Simple in addition to implementable algorithms Local algorithms Geometry, metrics, bounded growth, etc. Applications Unstructured P2P: Who should I connect to How do I figure out that the yellow node is farther away Idea: Cluster the network using a generalized MIS (-net). “Structuring Unstructured P2P Networks”. Stefan Schmid, Roger Wattenhofer, in submission. unstructured P2P Overview Introduction Past Present Dynamic systems & mobility Fault-tolerance (crash failures) Security (Byzantine failures) Selfish agents & computational economy Simple in addition to implementable algorithms Local algorithms Geometry, metrics, bounded growth, etc. Applications

Questions Comments Distributed Computing Group Roger Wattenhofer

Gardiner, Bryan Contributing Reporter/Writer

Gardiner, Bryan is from United States and they belong to Wired News and they are from  San Francisco, United States got related to this Particular Journal. and Gardiner, Bryan deal with the subjects like Computers; Information Technology Industry

Journal Ratings by Pennsylvania State University-Penn State Dubois

This Particular Journal got reviewed and rated by Pennsylvania State University-Penn State Dubois and short form of this particular Institution is PA and gave this Journal an Excellent Rating.