一概念
1.Totally-ordered multicast (5pt)
A multicast operation by which all messages are delivered in the same order to each receiver.
2.Scalability (5pt)
scalability is the ability of a system, network, or process to handle a growing amount of work in a capable manner or its ability to be enlarged to accommodate that growth.
3.Availability & Reliability (5pt)
Availability: Readiness for usage。说明系统已准备好，马上就可以使用。通常，它指在
任何给定的时刻，系统都可以正确地操作，可根据用户的行为来执行它的功能。换句
话说，高度可用的系统在任何给定的时刻都能及时地工作。
Reliability: Continuity of service delivery 。指系统可以无故障地持续运行。与可用性相反，可靠性是根据时间间隔而不是任何时刻来进行定义的。
4.Omission failures (5pt)
//当服务器不能对请求进行响应时就发生遗漏性故障。
A component fails to respond to incoming requests.
Receive omission: Fails to receive incoming messages.
Send omission: Fails to send messages
5.Bully Algorithm (5pt) P451
6.Primary-back protocols (5pt)
Protocols that allow processes to perform read operations on a locally available copy ,but should forward write operations to a (fixed) primary copy.
7.CDN (Content Delivery Networks) (5pt)
8.Distributed System (5pt)
9.Dynamic binding (5pt)
动态绑定是指在执行期间（非编译期）判断所引用对象的实际类型，根据其实际的类型调用其相应的方法。程序运行过程中，把函数（或过程）调用与响应调用所需要的代码相结合的过程称为动态绑定。
10.Vector timestamp (5pt)
时间戳是指文件属性里的创建、修改、访问的时间。可以捕获因果关系的向量时钟中的时间戳称为向量时间戳。
https://www.doczj.com/doc/4c5012341.html,yered Software Architecture (5pt)
层次式软件体系结构是把大型软件系统按照功能的扩展性，分成若干层，最内层为“内核”，完成最为基本的公用操作（例如对物理数据库的存取）。向外各层逐渐进行功能扩展，满足用户不同系统规模的需求。
12.Overlay network
that is , a network in which the nodes are formed by processes and the links represent the possible communication channels (which are usually realized as TCP connections). In general, a process cannot communicate directly with an arbitrary other process, but is required to send messages through the available communication channels.
二大题
1. Explain what is meant by transparency, and give examples of different types of transparency. We argued that distribution transparency may not be in place for pervasive systems. This statement is not true for all types of transparencies. Give an example. (6pt)
Distribution transparency is the phenomenon by which distribution aspects in a system are hidden from users and applications. Examples include access transparency, location transparency, migration transparency, relocation transparency, replication transparency, concurrency transparency, failure transparency, and persistence transparency.
Think of migration transparency. In many pervasive systems, components are mobile and will need to re-establish connections when moving from one access point to another. Preferably, such handovers should be completely transparent to the user. Likewise, it can be argued that many other types of transparencies should be supported as well. However, what should not be hid-den is a user is possibly accessing resources that are directly coupled to the user's current environment.
2. Explain which functions are implemented in the runtime library of an RPC system. See also the following figure. (8pt)
The library typically consists of (configurable) send and receive primitives, such as parameterized primitives for socket communication. In addition, we should expect to see all kinds of routines for converting machine-dependent data structures into network- and machine neutral representations.
3. Please explain the recursive lookups and iterative lookups when resolving the name in distributed systems. What are major drawbacks of recursive lookups when resolving a key in a DHT-based system? (8pt)
Interactive – client drives the resolution：Caching by clients；Potentially costly communications。Recursive – the server does：Higher performance demand on servers；More effective caching；Reduced communication costs。
You can’t ask for all nodes in a subdomain (but very few people were doing this anyway).
A problem is that the requesting client will never be able to discover what went wrong when no answer is returned. Somewhere along the route that cor-responds to resolving the key, a message may have been lost or a node may have failed. For this reason, an iterative lookup is sometimes preferred: the client will know exactly which part of the lookup did not come through and may be able to choose an alternative node to help out.
4. In Fig we have two ELECTION messages circulating simultaneously. While it does no harm to have two of them, it would be more elegant if one could be killed off. Devise an algorithm for doing this without affecting the operation of the basic election algorithm. (8pt)
进程P1和P2同时发现以前的协作者崩溃，则：
(1)P1向P2发送一个ELECTION消息；
(2)若无人响应，则P1获胜，转步骤（4）；
(3)若P2编号大于P1,则P2获胜，转步骤（4）；
(4)获胜进程使用环算法进行选举。
5. What kind of consistency would you use to implement an electronic stock market? Explain your answer. (6pt)
Causal consistency is probably enough. The issue is that reactions to changes in stock values should be consistent. Changes in stocks that are independent can be seen in different orders.
6. Why is the following data store not sequentially consistent? Is it causally consistent? Be sure to explain your answer. (6pt)
P1: W(x)a
---------------------------------------------
P2: W(x)b
---------------------------------------------
P3: R(x)b R(x)a
---------------------------------------------
P4: R(x)a R(x)b
It is not sequentially consistent because P3 and P4 are reading the effects of concurrent writes (by respectively P1 and P2) in different orders. It is causally consistent because there are no causal relationships that need to be obeyed.
7. (8pt) Explain the values for the finger table of node 9 in the following Chord DHT-based system. Assume node 4 is requested to look up key 29. How is this key resolved? You must explain your answer.
FP p[i]=succ(p+2i-1), with i ≥1. In this example FP9[1]= succ(9+20)=succ(10) =11. Likewise FP9[2]= succ(9+2)= succ(11)= 11 ,and so on.
Node 4 will first look for the entry that satisfies FT4[j] ≤ 29< FT4[j+1], which in this example is entry 5 ,where we need to apply modulo arithmetic. Therefore ,the request is forwarded to node20, which will then, for similar reasons, forward it to node 28. Node 28 will find that 29 lies between
28 (its own ID) and FT28[1], so that it sends the request to node 1. The latter is responsible for key
29.
8. (6pt) Please describe the five different classes of failures can occur in RPC systems, and give the some solutions to solve the failures.
(1) The client is unable to locate the server.
(2) The request message from the client to the server is lost.
(3) The server crashes after receiving a request.
(4) The reply message from the server to the client is lost.
(5) The client crashes after sending a request.
(1)to have the error raise an exception.
(2)just have the operating system or client stub start a timer when sending the request. If the
timer expires before a reply or acknowledgment comes back, the message is sent again.
(3)to wait until the server reboots (or rebind to a new server) and try the operation again./gives
up immediately and reports back failure. to guarantee nothing. /When a server crashes, the client gets no help and no promises about what happened.
(4)to guarantee nothing. When a server crashes, the client gets no help and no promises about
what happened./ to try to structure all the requests in an idempotent way./ to have the client assign each request a sequence number.
(5)before a client stub sends an RPC message/reincarnation/gentle reincarnation/expiration
9. (6pt) For each of the following applications, do you think at-least-once semantics or at most once semantics is best? Discuss:
(a)Reading and writing files from a file server
(b)Compiling a program
(c)Remote banking
For (a) and (b), at least once is best. There is no harm trying over and over. For (c), it is best to give it only one try. If that fails, the user will have to intervene to clean up the mess.
10. Consider an unstructured overlay network in which every node randomly chooses
C neighbors. To search for a file, a node floods a request to its neighbors and requests those to flood the request once more. How many nodes will be reached? (8pt)
Consider a network of N nodes. If each node chooses c neighbors at random, then the probability that P will choose Q, or Q chooses P is roughly 2c/(N-1).
11. (10pt) Sketch designs for a home system consisting of a separate media sever that will allow for the attachment of a wireless client. Then latter is connected to audio/video equipment and transforms the digital media streams to analog output. The server runs on a separate machine, possibly connected to the Internet, but also no keyboard and/or monitor connected. Please explain the main technologies we would use in this home system.