Part Ⅰ General 3
1 Elements 3
1.1 Top Systems Conferences/Journals 3
1.2 How to Read a Research Paper 5
1.3 How to Write a Research Paper 6
1.3.1 Abstract 6
1.3.2 Introduction 6
1.3.3 Background Information/Problem Statement 6
1.3.4 Your Approach 6
1.3.5 Implementation 6
1.3.6 Performance Evaluation 7
1.3.7 Related Work 7
1.3.8 Conclusions 7
1.3.9 Acknowledgement 7
1.3.10 References 8
1.3.11 Most Common Mistakes in Paper Writing 8
1.4 How to Give a Presentation 9
1.4.1 General Approach 9
1.4.2 Understanding the Paper 10
1.4.3 Adapting the Paper for Presentation 10
1.4.4 Slides 11
1.4.5 The Dry-Run 12
1.4.6 To Memorize or not to Memorize? 13
1.4.7 You Are on the Stage 13
1.4.8 Interacting with the Audience and Dealing with Questions 14
1.5 Final Words:On Being a Scientist 14
References 15
2 Rules of Thumb 16
2.1 Rules of Thumb 16
2.2 Further Readings 17
References 17
Part Ⅱ Design 21
3 Bloom Filters 21
3.1 Introduction 21
3.2 Standard Bloom Filters 22
3.2.1 Basic Idea of Bloom Filters 22
3.2.2 False Positive Rate Estimation 23
3.2.3 Optimal Number of Hash Functions 23
3.2.4 Another Method of Implementing 24
3.3 Counting Bloom Filters 25
3.4 Compressed Bloom Filters 27
3.5 D-left Counting Bloom Filters 28
3.5.1 D-left Hashing 28
3.5.2 D-left Counting Bloom Filters 29
3.5.3 Performance 30
3.6 Spectral Bloom Filters 31
3.6.1 Basic Principle of SBF 31
3.6.2 SBF Frequency Query Optimization 33
3.7 Dynamic Counting Bloom Filters 33
3.8 Case Studies 34
3.8.1 Case Study 1:Summary Cache 35
3.8.2 Case Study 2:IP Traceback 36
3.9 Conclusion 36
References 37
4 Distributed Hash Tables 38
4.1 Introduction 38
4.2 An Overview of DHT 39
4.3 The Overlay Network of DHT 40
4.4 Chord:An Implementation of DHT 42
4.4.1 Topology of Chord 42
4.4.2 Key Lookup in Chord 42
4.4.3 Dynamic Updates and Failure Recovery 44
4.5 Case Study 1:Cooperative Domain Name System(CoDoNS) 46
4.5.1 Background and Motivation 46
4.5.2 Overview of the System 47
4.5.3 DHT in CoDoNS 47
4.5.4 Evaluation 48
4.6 Case Study 2:Cooperative File System(CFS) 48
4.6.1 Background and Motivation 48
4.6.2 Overview of the System 49
4.6.3 DHT in CFS 49
4.6.4 Evaluation 49
References 50
5 Locality Sensitive Hashing 52
5.1 Introduction 52
5.1.1 Basic Idea of LSH 52
5.1.2 The Origin of LSH 53
5.2 Overview 53
5.2.1 The Definition 53
5.2.2 Properties of LSH 54
5.2.3 Several LSH Families 54
5.2.4 Approximate Nearest Neighbor 58
5.3 Case Study 1:Large-Scale Sequence Comparison 60
5.3.1 Theory 60
5.3.2 Algorithm Complexity 61
5.3.3 Implementation Details 61
5.3.4 Results 62
5.4 Case Study 2:Image Retrieval 62
5.4.1 Motivation 62
5.4.2 The Problems of Existing Approaches 62
5.4.3 The System 63
5.4.4 Results 63
References 63
6 XOR Operations 65
6.1 Introduction 65
6.2 XOR Operation 65
6.2.1 Truth Table 66
6.2.2 Set Diagrams 66
6.3 XOR Properties 66
6.4 Compress with XOR 67
6.4.1 Case Study 1:XOR-linked list 67
6.4.2 Case Study 2:XOR swap algorithm 68
6.5 Fault Tolerance 68
6.5.1 Case Study 3:Hamming(7,4)code 68
6.5.2 Hamming Codes with Additional Parity 70
6.5.3 Case Study 4:RAID 70
6.6 Case Study 5:Feistel Cipher 71
6.7 Case Study 6:Kademlia 72
6.7.1 XOR Metric in Kademlia 73
6.7.2 Routing Table in Kademlia 74
6.7.3 Kademlia Protocol 74
6.8 Conclusion 75
References 76
7 Adaptation 77
7.1 Introduction 77
7.2 How Adaptation Works and Key Issues 78
7.2.1 How Does Adaptation Work? 78
7.2.2 Classification of Adaptation 80
7.3 Case Studies 83
7.3.1 Case Study 1:Adaption in Internet Routing System 83
7.3.2 Case Study 2:Adaptive Self-Configuration for Sensor Networks 87
References 90
8 Optimistic Replication 92
8.1 Introduction 92
8.2 Topic Description 94
8.2.1 Design Considerations 94
8.2.2 Techniques and Algorithms 95
8.3 Case Studies 100
8.3.1 Case Study 1:The Notes System 100
8.3.2 Case Study 2:The Bayou system 102
References 106
9 Reputation and Trust 107
9.1 Introduction 107
9.2 Reputation Systems:Challenges and Models 108
9.2.1 Challenges 108
9.2.2 Reputation Models 109
9.2.3 Threat Model 113
9.3 Comparison of Representative Work 114
9.4 Case Studies 116
9.4.1 Case Study 1:EigenTrust 117
9.4.2 Case Study 2:HOURS 117
9.5 Conclusion 118
References 118
10 Moving Average 120
10.1 Introduction 120
10.2 Topic Description 120
10.2.1 Simple Moving Average 121
10.2.2 Cumulative Moving Average 121
10.2.3 Weighted Moving Average 121
10.2.4 Exponential Weighted Moving Average 122
10.3 Case Study 1:Attacks Detection 123
10.3.1 Introduction of Denial of Service Attack 123
10.3.2 Anomalies Detection 124
10.3.3 SYN Flooding Detection 126
10.3.4 Other Methods 126
10.4 Case Study 2:Machine Monitoring Technique 127
10.5 Case Study 3:Data Cleaning in Wireless Sensor Networks 130
10.6 Conclusion 132
References 132
11 Machine Learning 134
11.1 Machine Learning Concepts 134
11.1.1 Concepts and History 135
11.2 Introduction of Machine Learning 136
11.2.1 A Typical Machine Learning Problem 136
11.2.2 Machine Learning in Computer Systems Research 139
11.3 Machine Learning Techniques 140
11.3.1 Category 140
11.3.2 Machine Learning Techniques and Algorithms 142
11.4 Case Studies 145
11.4.1 Case Study 1:Large-Scale System Problem Detection 145
11.4.2 Case Study 2:Snitch 146
11.5 Conclusion 147
References 148
Part Ⅲ Implementation 153
12 Asynchronous I/O 153
12.1 Motivation 153
12.2 I/O Multiplexing 155
12.3 Asynchronous I/O 158
12.3.1 Linux Asynchronous I/O 158
12.3.2 Windows Overlapped I/O 164
12.4 Conclusion 172
References 172
13 Multithreading 173
13.1 Background 173
13.2 The Concept of Thread 174
13.3 Hardware Support for Multithreading 175
13.3.1 Block Multithreading 175
13.3.2 Interleaved Multithreading 176
13.3.3 Simultaneous Multithreading 176
13.4 Multithreading Programming 176
13.4.1 POSIX Threads(Pthreads) 177
13.4.2 JAVA Threads 178
13.4.3 WIN32 Threads 178
13.4.4 Common APIs 180
13.5 Multithreading Synchronization 184
13.5.1 Multithreading Synchronization Problems 184
13.5.2 Mutual Exclusion 185
13.5.3 Solutions of Mutual Exclusion 186
13.5.4 Mutual Exclusion Cases 187
13.6 Case Studies 188
13.7 Conclusion 199
References 189
14 Virtualization 191
14.1 Virtualization Definitions 191
14.2 A Brief History of Virtualization 192
14.2.1 The Mainframe Virtualization 193
14.2.2 The x86 Virtualization 193
14.3 Why Virtualization? 194
14.4 Virtualization Capabilities 196
14.5 The Benefits of Virtualization 196
14.5.1 Increasing Utilization 196
14.5.2 Reducing Cost 197
14.5.3 Isolation 197
14.5.4 Improving Application Development Process 197
14.5.5 Business Continuity 198
14.5.6 Manageability,Scalability and Flexibility 198
14.6 Types of Virtualization 199
14.7 Virtualization Vendors and Products 201
14.8 Case Studies 201
14.8.1 Case Study 1:JVM 202
14.8.2 Case Study 2:VirtualPower 204
14.9 Issues of Virtualization 205
14.9.1 Issues of Adopting Virtualization 205
14.9.2 Issues of Providing Virtualization 206
References 208
Part Ⅳ Evaluation 213
15 Queueing Theory 213
15.1.1 Queueing Models 214
15.2 Fundamental Concepts 216
15.2.1 Useful Probability Distributions 216
15.2.2 Markov Chain 218
15.3 Queueing Systems 219
15.3.1 Markovian Queues 220
15.3.2 Non-Markovian Queues 224
15.4 Queueing Networks 226
15.5 Case Studies 227
15.5.1 Case Study 1:Telephone Systems 227
15.5.2 Case Study 2:A Barber Shop 227
References 229
16 Black Box Testing 230
16.1 Introduction 230
16.2 Black Box Testing Techniques 231
16.2.1 Equivalence Partitioning 231
16.2.2 Boundary Value Analysis 232
16.2.3 Decision Table Testing 232
16.2.4 Pairwise Testing 233
16.2.5 State Transition Tables 233
16.2.6 Use Case Testing 234
16.3 Other Methods of Software Testing 234
16.4 Case Studies 235
16.4.1 Case Study 1:Web Services 235
16.4.2 Case Study 2:MobileTest 239
References 242
17 Goodness-of-Fit 244
17.1 Introduction 244
17.2 General Topics in Goodness-of-Fit 245
17.2.1 Hypothesis Testing 246
17.2.2 Definition 247
17.2.3 Common Problems in Goodness-of-Fit Tests 247
17.2.4 Quantitative Goodness-of-fit Techniques 249
17.3 Chi-Square Test 249
17.3.1 Meaning of the Chi-Square Test 250
17.3.2 Definition of Chi-Square 251
17.4 Kolmogorov-Smirnov test 254
17.4.1 How Does K-S Test Work? 255
17.4.2 Comparison of Chi-Square and Kolmogorov-Smirnov Tests 261
17.5 Case Studies 262
17.5.1 Case Study 1:Object Characteristics of Dynamic Web Content 262
17.5.2 Case Study 2:Failures in High-Performance Computing Systems 263
References 263
Index 265