An Introduction to Models of Online Peer-to-Peer Social Networking (Synthesis Lectures on Communication Networks)

This book concerns peer-to-peer applications and mechanisms operating on the Internet, particularly those that are not fully automated and involve significant human interaction. So, the realm of interest is the intersection of distributed systems and online social networking. Generally, simple models are described to clarify the ideas. Beginning with short overviews of caching, graph theory and game theory, we cover the basic ideas of structured and unstructured search. We then describe a simple framework for reputations and for iterated referrals and consensus. This framework is applied to a problem of sybil identity management. The fundamental result for iterated Byzantine consensus for a relatively important issue is also given. Finally, a straight-forward epidemic model is used to describe the propagation of malware on-line and for BitTorrent-style file-sharing. This short book can be used as a preliminary orientation to this subject matter. References are given for the interested student to papers with good survey and tutorial content and to those with more advanced treatments of specific topics. For an instructor, this book is suitable for a one-semester seminar course. Alternatively, it could be the framework for a semester's worth of lectures where the instructor would supplement each chapter with additional lectures on related or more advanced subject matter. A basic background is required in the areas of computer networking, probability theory, stochastic processes, and queueing. Table of Contents: Networking overview / Graphs / Games / Search in structured networks / Search in unstructured networks / Transactions, reputations, and referrals / False Referrals / Peer-to-peer file sharing / Consensus in dynamical belief systems / Byzantine consensus / Epidemics Preface......Page 13 Background......Page 15 The Internet......Page 17 The client-server world-wide web (WWW)......Page 23 Adaptive and distributed caching......Page 24 Identity authentication......Page 29 Peer-to-peer (p2p) social applications online......Page 30 Graphs......Page 31 Social graph models and attributes......Page 32 Discussion: edge and vertex churn......Page 39 Set-up for non-cooperative games......Page 41 Symmetric altruism......Page 43 Games with collective outcomes......Page 48 Summary......Page 51 Peer-to-Peer Search......Page 53 Distributed hash tables (DHTs)......Page 55 A small worlds case......Page 56 Load balancing......Page 59 Discussion......Page 61 Forwarding with privacy......Page 62 Single threaded search by random walk......Page 65 Popularity biased random walks......Page 67 Discussion......Page 68 Reputations and Referrals......Page 69 Accrued reputations......Page 71 Referrals in distributed peer-to-peer systems......Page 72 Discussion......Page 74 Sybils......Page 75 Sybil-resistant one-step referrals......Page 76 Discussion......Page 78 Overview of BitTorrent......Page 79 File segmentation......Page 80 Discussion......Page 84 Consensus......Page 87 Nearest neighbor averaging......Page 89 Convergence of consensus......Page 90 Gibbs invariant of a Markov random field......Page 91 The tree data structure......Page 93 Leaves-to-root majority voting......Page 94 Fundamental consensus performance result......Page 95 Discussion......Page 96 Models of disease spread in living populations......Page 99 Epidemics spread by social engineering......Page 103 Online disease......Page 105 Summary: selecting potential victims......Page 109 Bibliography......Page 111 Author's Biography......Page 125 Part I. Background 1. Networking overview The internet The client-server world-wide web (WWW) Adaptive and distributed caching Identity authentication Peer-to-peer (p2p) social applications online 2. Graphs Basic graphical terms Social graph models and attributes Discussion: edge and vertex churn 3. Games Set-up for non-cooperative games Symmetric altruism Games with collective outcomes Summary Part II. Peer-to-peer search 4. Search in structured networks Distributed hash tables (DHTs) A small worlds case Load balancing Discussion Forwarding with privacy 5. Search in unstructured networks Single threaded search by random walk Popularity biased random walks Discussion Part III. Reputations and referrals 6. Transactions, reputations, and referrals Accrued reputations Referrals in distributed peer-to-peer systems Discussion 7. False referrals Sybils Sybil-resistant one-step referrals Discussion 8. Peer-to-peer file sharing Overview of BitTorrent File segmentation Discussion Part IV. Consensus 9. Consensus in dynamical belief systems Nearest neighbor averaging Convergence of consensus Gibbs invariant of a Markov random field 10. Byzantine consensus The tree data structure Information gathering to determine input(v) Leaves-to-root majority voting Fundamental consensus performance result Discussion 11. Epidemics Models of disease spread in living populations Epidemics spread by social engineering Online disease Summary: selecting potential victims Bibliography Author's biography. Examines peer-to-peer applications and mechanisms operating on the Internet, particularly those that are not fully automated and involve significant human interaction. So, the realm of interest is the intersection of distributed systems and online social networking. Generally, simple models are described to clarify the ideas.