计算机系统研究基础（国内英文版）

　　自从计算机问世以来，计算机系统结构的研究重点发生了很多变化，这让一些希望从事这方面研究的新手觉得很难入门。作者根据多年从事研究和指导研究生的经验，把计算机系统研究中最常用的原理和关键技术汇集在一起。在基本知识部分，作者描述了从事系统结构研究的基本要领，包括如何读、写、说，以及英文写作最常见的问题，并给出了12个最经典的设计原理和经验。在关键技术部分，作者从建模、设计、实现和性能评测方面选择了15个关键技术进行了详细的讨论和描述，每一个关键技术的题目都经过精心挑选，并且提供多个实例分析。《计算机系统研究基础（英文版）》可供计算机系统结构初学者使用，也可供高年级本科生和研究生在学习有关课程时参考。

　　施巍松，美国韦恩州立大学计算机科学系副教授，移动和因特网系统结构实验室主任，可持续计算实验室主任。美国国家科学基金会杰出青年教授奖获得者，全国百篇优秀博士论文获得者。IEEE资深会员，IEEE Internet Computing及Joumal of Parallel and Distriibuted Computinq客座编辑，Journal of Computer Scierice and Techology及International Journal of Sensor Networks编委。施巍松博士的研究兴趣包括计算机系统和可持续计算等。

Part I General
Elements
1.1 Top Systems Conferences/Journals
1.2 How to Read a Research Paper
1.3 How to Write a Research Paper
1.3.1 Abstract
1.3.2 Introduction
1.3.3 Background Information/Problem Statement
1.3.4 Your Approach
1.3.5 Implementation
1.3.6 Performance Evaluation
1.3.7 Related Work
1.3.8 Conclusions
1.3.9 Acknowledgement
1.3.10 References
1.3.11 Most Common Mistakes in Paper Writing
1.4 How to Give a Presentation
1.4.1 General Approach
1.4.2 Understanding the Paper
1.4.3 Adapting the Paper for Presentation
1.4.4 Slides
1.4.5 The Dry-Run
1.4.6 To Memorize or not to Memorize?
1.4.7 You Are on the Stage
1.4.8 Interacting with the Audience and Dealing with Questions
1.5 Final Words： On Being a Scientist
References
2 Rules of Thumb
2.1 Rules of Thumb
2.2 Further Readings
References
Part Ⅱ Design
3 Bloom Filters
3.1 Introduction
3.2 Standard Bloom Filters
3.2.1 Basic Idea of Bloom Filters
3.2.2 False Positive Rate Estimation
3.2.3 Optimal Number of Hash Functions
3.2.4 Another Method of Implementing
3.3 Counting Bloom Filters
3.4 Compressed Bloom Filters
3.5 D-left Counting Bloom Filters
3.5.1 D-left Hashing
3.5.2 D-left Counting Bloom Filters
3.5.3 Performance
3.6 Spectral Bloom Filters
3.6.1 Basic Principle of SBF
3.6.2 SBF Frequency Query Optimization
3.7 Dynamic Counting Bloom Filters
3.8 Case Studies
3.8.1 Case Study 1： Summary Cache
3.8.2 Case Study 2： IP Traceback
3.9 Conclusion.
References
4 Distributed Hash Tables
4.1 Introduction
4.2 An Overview of DHT
4.3 The Overlay Network of DHT
4.4 Chord： An Implementation of DHT.
4.4.1 Topology of Chord
4.4.2 Key Lookup in Chord
4.4.3 Dynamic Updates and Failure Recovery
4.5 Case Study 1： Cooperative Domain Name System （CoDoNS）
4.5.1 Background and Motivation
4.5.2 Overview of the System
4.5.3 DHT in CoDoNS
4.5.4 Evaluation
4.6 Case Study 2： Cooperative File System （CFS）
4.6.1 Background and Motivation.
4.6.2 Overview of the System
4.6.3 DHT in CFS
4.6.4 Evaluation
References
5 Locality Sensitive Hashing
5.1 Introduction
5.1.1 Basic Idea of LSH
5.1.2 The Origin of LSH
5.2 Overview.
5.2.1 The Definition
5.2.2 Properties of LSH
5.2.3 Several LSH Families
5.2.4 Approximate Nearest Neighbor
5.3 Case Study 1： Large-Scale Sequence Comparison
5.3.1 Theory
5.3.2 Algorithm Complexity
5.3.3 Implementation Details
5.3.4 Results
5.4 Case Study 2： Image Retrieval
5.4.1 Motivation
5.4.2 The Problems of Existing Approaches
5.4.3 The System
5.4.4 Results
References
6 XOR Operations
6.1 Introduction
6.2 XOR Operation
6.2.1 Truth Table
6.2.2 Set Diagrams
6.3 XOR Properties
6.4 Compress with XOR
6.4.1 Case Study 1： XOR-linked list
6.4.2 Case Study 2： XOR swap algorithm.
6.5 Fault Tolerance
6.5.1 Case Study 3： Hamming （7，4） code
6.5.2 Hamming Codes with Additional Parity
6.5.3 Case Study 4： RAID
6.6 Case Study 5： Feistel Cipher
6.7 Case Study 6： Kademlia
6.7.1 XOR Metric in Kademlia
6.7.2 Routing Table in Kademlia
6.7.3 Kademlia Protocol
6.8 Conclusion.
References
7 Adaptation
8 Optimistic Replication.
9 Reputation and Trust
10 Moving Average
Part Ⅲ Implementation
Part Ⅳ Evalution