Peer-to-Peer Computing (eBook)

Quang Hieu Vu is currently a Research Fellow at Institute for Infocomm Research (I2R), Singapore. He obtained his PhD degree from the Singapore-MIT Alliance in 2008. Before joining I2R, he was respectively a Research Fellow at National University of Singapore and Imperial College London. His research interests include peer-to-peer, information retrieval, and network security. Mihai Lupu has been a post-doctoral research fellow with the Information Retrieval Facility in Vienna, Austria, since October 2008. He has recently received his PhD degree from the Singapore-MIT Alliance at the National University of Singapore, where he has worked mostly on Information Retrieval on Peer-to-Peer Networks. His research interests include information retrieval and management, peer-to-peer and ad-hoc networks. Beng Chin Ooi is Professor of Computer Science at the National University of Singapore (NUS). He obtained his PhD from Monash University, Australia, in 1989. He has served as a PC member for international conferences including ACM SIGMOD, VLDB, IEEE ICDE, WWW, SIGKDD and is the recipient of ACM SIGMOD 2009 Contributions award and an IEEE fellow. His research interests include database performance issues, indexing techniques, multimedia and spatio-temporal databases, P2P systems and advanced applications, and data intensive scalable computing.  

Preface 5
Organization of the Book 6
Acknowledgements 8
Contents 9
Introduction 15
Peer-to-Peer Computing 15
Potential, Benefits, and Applications 17
Challenges and Design Issues 21
P2P vs. Grid Computing 22
Summary 24
Architecture of Peer-to-Peer Systems 25
A Taxonomy 26
Centralized P2P Systems 27
Decentralized P2P Systems 27
Hybrid P2P Systems 29
Centralized P2P Systems 29
Napster: Sharing of Digital Content 31
About SETI@home 32
Fully Decentralized P2P Systems 34
Properties 35
Gnutella: The First "Pure" P2P System 36
Properties 36
PAST: A Structured P2P File Sharing System 38
Properties 38
Canon: Turning Flat DHT into Hierarchical DHT 40
Properties 42
Skip Graph: A Probabilistic-Based Structured Overlay 42
Properties 44
Hybrid P2P Systems 45
BestPeer: A Self-Configurable P2P System 46
Summary 50
Routing in Peer-to-Peer Networks 52
Evaluation Metrics 53
Routing in Unstructured P2P Networks 53
Basic Routing Strategies 54
Breadth-First Search 54
Depth-First Search 54
Heuristic-Based Routing Strategies 56
Iterative Deepening 56
Directed BFS and Intelligent Search 57
Local Indices Search 58
Routing Indices-Based Search 59
Random Walk 60
Adaptive Probabilistic Search 61
Bloom Filter Based Search 61
Interest-Based Shortcuts 62
Routing in Structured P2P Networks 63
Chord 65
CAN 69
PRR Trees, Pastry and Tapestry 71
Viceroy 76
Crescendo 77
Skip Graph 78
SkipNet 80
P-Grid 80
P-Tree 82
BATON 84
Routing in Hybrid P2P Networks 86
Hybrid Routing 86
Edutella 87
Ultrapeers 89
Structured Superpeers 90
Summary 91
Data-Centric Applications 94
Multi-Dimensional Data Sharing 95
VBI-Tree 97
Mercury 99
SSP 101
High-Dimensional Indexing 103
CISS 104
ZNet 105
M-Chord 107
SIMPEER 109
LSH Forest 110
Textual Information Retrieval 111
Basic Techniques 113
Query and Document Representation 113
Directory Management 114
Ranking of Results 116
Improving the Performance of Information Retrieval 116
PlanetP 117
Summary Index 119
pSearch 120
PRISM 122
Structured Data Management 124
Query Processing in Heterogeneous Data Sources 125
Semantics 125
Mapping Heterogeneous Data Sources 126
Query Processing over Relational Databases 128
Query Processing over XML Documents 129
Unstructured Keyword Query Processing over Relational Databases 130
Indexing Schemes 131
Piazza 131
Peer-Programming Language 132
Query Reformulation Algorithm 133
Hyperion 134
Mapping Table Construction 134
Query Processing 136
PeerDB 136
Table-to-Query Similarity Measurement 137
Query Processing 137
Summary 138
Load Balancing and Replication 140
Load Balancing 141
When Load Balancing is Triggered 141
Dynamic Load Balancing 141
Static Load Balancing 142
The Power of Two Choices 143
How Load Balancing is Performed 144
Load Balancing in Concrete Systems 145
Basic Load Balancing Schemes with Virtual Nodes 145
One-to-One Scheme 145
One-to-Many Scheme 146
Many-to-Many Scheme 146
Y0 Protocol 147
The S& M Protocol
The Design of the S& M Protocol
A Combination of Both Local and Random Probes 150
Load Imbalance Boundary 150
Mercury 150
Load Balancing with Histograms 151
Online Balancing of Range-partitioned Data 152
Replication 153
Replica Granularity 153
Full Replication 154
Block Replication 154
Replica Quantity 155
Uniform Replication 155
Proportional Replication 155
Square-root Replication 155
Replica Distribution 156
Replica Consistency 157
Replication with Expiration 157
Immediate Updates 157
Replica Replacement 157
Minimum Relative Size 158
Replication in Concrete Systems 158
Replication in Read-only Unstructured P2P Systems 158
Replication in Read-only Structured P2P Systems 158
Past 158
Cooperative File System 159
Beehive 160
Analytical Model 160
Replication 161
Symmetric Replication for Structured Peer-to-Peer Systems 162
Node Grouping 162
Data Replication 162
CUP: Controlled Update Propagation in Peer-to-Peer Networks 163
System Architecture 163
Data Replication 163
Dynamic Replica Placement for Scalable Content Delivery 164
Disseminating Tree Construction 164
Disseminating Tree Maintenance 165
Updates in Highly Unreliable, Replicated P2P Systems 165
Proactive Replication 167
Replication Protocol Design 167
Summary 168
Security in Peer-to-Peer Networks 170
Routing Attacks 170
Incorrect Lookup Routing 171
Incorrect Routing Updates 171
Incorrect Routing Network Partition 171
Secure Routing Scheme 172
Storage and Retrieval Attacks 173
Denial-of-Service Attacks 175
Managing Attacks 176
Detecting and Recovering from Attacks 177
Other Attacks 179
Data Integrity and Verification 179
Verifying Queries in Relational Databases 180
Self-verifying Data with Erasure Code 183
Verifying Integrity of Computation 184
Free Riding and Fairness 185
Quota-Based System 186
Trading-Based Schemes 187
Distributed Auditing 188
Incentive-Based Schemes 189
Adaptive Topologies 191
Privacy and Anonymity 192
PKI-Based Security 194
Summary 195
Trust and Reputation 196
Concepts 197
Trust Definitions 197
What is Trust 197
Trust in the View of Psychology 197
Trust in the View of Sociology 197
Trust in a Broader View 198
Trust Types 198
Trust in Action 198
Trust in Recommendation 198
Trust Values 199
Single Value 199
Binary Values 199
Multiple Values 199
Continuous Values 200
Trust Properties 200
Autonomy 200
Asymmetry 200
Transitivity 201
Composability 201
Trust Models 201
Trust Model Based on Credentials 202
Trust Model Based on Reputation 202
Trust Systems Based on Credentials 203
PolicyMaker 203
System Architecture 204
The PolicyMaker Language 204
Query Processing 205
Trust-X 205
System Architecture 205
Trust Systems Based on Individual Reputation 207
P2PRep 207
Basic Polling Protocol 207
Enhanced Polling Protocol 208
XRep 209
Cooperative Peer Groups in NICE 210
Trust Evaluation 210
Finding Paths Between Two Nodes in the Trust Graph 211
PeerTrust 211
General Trust Metric 212
Trust Systems Based on Both Individual Reputation and Social Relationship 213
Regret 213
Individual Dimension 213
Social Dimension 213
Ontology Dimension 213
NodeRanking 215
Social Network Construction 215
Reputation Evaluation 215
NodeRanking Algorithm 215
Trust Management 216
Server Based Trust Management 216
Gossiping Based Trust Management 217
Structured P2P Based Trust Management 217
XenoTrust 218
Architecture 220
EigenRep 220
Local Reputation 221
Global Reputation 221
Trust Management with P-Grid 223
Trust Evaluation 223
P-Grid Based Trust Management 223
Summary 225
P2P Programming Tools 228
Low Level P2P Programming 228
Sockets 229
Remote Procedure Call 229
Web Services 230
High Level P2P Programming 230
JXTA 231
Implementations 232
Protocols 232
Adding Value to the Network 233
Other Considerations 233
BOINC 234
P2 235
The Specification Language: NDlog 235
The Execution Framework 236
Mace 236
OverlayWeaver 236
Microsoft's Peer-to-Peer Framework 237
Deployment and Testing Environments 238
PlanetLab 238
Participating in PlanetLab 238
Application Deployment on PlanetLab 239
Emulab 239
Interfacing Emulab and PlanetLab 240
Amazon.com 240
Summary 240
Systems and Applications 242
Classic File Sharing Systems 242
Napster 242
Overview 242
How Napster Works 243
Protocol 244
Litigation: an Issue Beyond Technology 246
Gnutella 246
Overview of Gnutella 246
Protocol 248
Challenges 249
Freenet 250
Freenet Working Mechanisms 251
Freenet Protocol 254
Merits and Limitations 256
Peer-to-Peer Backup 256
pStore 257
A Cooperative Internet Backup Scheme 260
Pastiche 261
Samsara-Fairness for Pastiche 263
Other Systems 264
Analysis of Existing Systems 265
Data Management 267
Architectures for P2P Data Management Systems 267
PIER 267
BestPeer 269
XML Content Routing Network 271
Mesh-based Content Routing 271
View Selection 272
XML Data Filtering 273
Continuous Query Processing 273
PeerCQ 274
CQ-Buddy 274
Medusa 275
Peer-to-Peer-Based Web Caching 275
Background of Web Caching 275
Squirrel 276
Pastry: The Supporting P2P Infrastructure 277
How Squirrel Works 277
BuddyWeb: A P2P-based Collaborative Web Caching System 279
Architecture of BuddyWeb 280
Similarity-Based Reconfiguration 281
Similarity-based Routing and Self-adaptive Hopping 282
Communication and Collaboration 283
Instant Messaging 283
Jabber 283
Jingle 284
Serverless Communication 284
Skype 284
Distributed Collaboration 285
JBuilder 285
MS Groove 285
Collanos Workspace 286
Mobile Applications 286
Communication Applications 286
File Sharing Applications 287
Peer-to-Peer in Spirit 288
Peer-to-Peer in Implementation 288
Summary 289
Conclusions 291
Summary 291
Architecture 291
Routing and Resource Discovery 292
Data-Centric Applications 293
Load Balancing and Replication 294
Programming Models 294
Security Problems 295
Trust Management 296
Potential Research Directions 297
Sharing Structured Databases 297
Security 298
Data Stream Processing 299
Testbed and Benchmarks 299
Applications in Industry 300
Supply Chain Management Case Study 301
Potential Issues 303
Queries 304
References 305
Index 321