• Ingen resultater fundet

TECHNICAL UNIVERSITY OF DENMARK

N/A
N/A
Info
Hent
Protected

Academic year: 2023

Del "TECHNICAL UNIVERSITY OF DENMARK"

Copied!
7
0
0

Indlæser.... (se fuldtekst nu)

Hele teksten

(1)

Course: Distributed Systems Course no. 02220 Aids allowed: NO AIDS ALLOWED

Exam duration: 4 hours

Weighting: TOPIC 1: 13%, TOPIC 2: 18%, TOPIC 3: 37%, TOPIC 4: 32%

Answers are evaluated according to correctness, completeness and conciseness (i.e., an- swers must be correct, complete and short). In case you think some specification is missing or ambiguous, just state your own specification/understanding and continue to solve the problem according to that.

The problems start on Page 2.

(2)

TOPIC 1 (13%): Architectural Styles and Design Chal- lenges

PROBLEM 1.1 (6%)

Client-server and peer-to-peer (p2p) are the two most well known architectural styles for distributed systems. Discuss the key differences between these two architectures in terms of: (i) symmetry/asymmetry. (ii) global/local knowledge of the system, (iii) centraliza- tion/decentralization, (iv) robustness, (v) scalability, (vi) costs.

PROBLEM 1.2 (2%)

A physical distributed infrastructure usually consists of a potentially large number of ma- chines interconnected by a network of arbitrary complexity. Aplacement strategy is crucial in terms of determining the properties of the distributed system (such as performance, re- liability, security, etc.). Describe 2 placement strategies in the context of a client server architectural style.

PROBLEM 1.3 (5%)

In order to design a real-world distributed system, a number of challenges need to be considered and overcome. The major challenges in distributed systems are showed in Figure 1. Describe the meaning of each of those challenges.

Figure 1: Challenges for Distributed Systems

(3)

TOPIC 2 (18%): Fault-Tolerant Protocols

PROBLEM 2.1 (11%)

Request-reply protocols can be implemented in different ways to provide different delivery guarantees. Combination of these choices can lead to a variety of possible semantics for the reliability of remote invocations as seen by the invoker. Well known examples of such semantics are: Maybe, At-least-once and At-most-once.

Question 1 (2%): Describe the main differences between these three remote invocation semantics.

Question 2 (2%): Discuss how these three semantics can be achieved in terms of fault- tolerance measures. In other words, what fault-tolerance mechanisms can be used to implement each of these semantics?

[Hint: you can start by filling in the following Table, and then discuss accordingly]

Error Type Error Control Mechanism Corruption of message

Loss of message Duplication of output Floating corps

Question 3 (7%): Provide a specification (in your preferred programming language or using pseudo-code) of a client-server system implementing a request-reply protocol compliant with the At-most-once semantics. Add comments in your specification to indicate where you use the needed fault-tolerance mechanisms.

PROBLEM 2.2 (7%)

In ACK/NACK protocols, it is the sender who takes the initiative for sending data, and the receiver merely responds to this. Effectively, this obliges the receiver to be able to receive data at any time after it has sent an acknowledgment. An alternative strategy is for the receiver to have the initiative, and for it explicitly to request data when it is able to receive them. In distributed systems jargon, this is known as polling.

Provide a specification (in your preferred programming language or using pseudo-code) of a fault-tolerantpolling protocol that protects against these three failures: loss, duplication and corruption of messages. Explain how the protocol deals with each of these failures.

(4)

TOPIC 3 (37%): Logical Time and Global States

PROBLEM 3.1 (10%)

Let→ be the Lamport happened-before relation, and L(e) denote the Lamport timestamp of event e at whatever process it occurred at. By considering a chain of zero or more messages connecting events e1 and e2 and using induction on the length of any sequence of events relating e1 and e2, prove that e1 →e2 ⇒L(e1)< L(e2).

PROBLEM 3.2(10%)

Let us consider a distributed system composed of three processesp1,p2 andp3. An example of the progress of a possible computation of the system is shown in Figure 2, where each event e is described by 5 components < p, s, s0, M, c >, meaning that process p goes from state s to state s0 because a message M was sent or received on channelc.

Figure 2: Computation of the Distributed System

Question 1 (2%): Using the computation in Figure 2, discuss an example of inconsistent set of events by:

a) drawing aninconsistent cut defining the inconsistent set b) explaining why the set is inconsistent.

Let us supposeChandy and Lamport’s snapshot algorithm is initiated by processp3 just before event e2 in the computation in Figure 2.

Question 2 (2%): Sketch how markers would be exchanged during the execution of the

(5)

Question 3 (2%): Which events are included in the resulting consistent set H of events?

Question 4 (2%): Which state components are noted down in the various processes, as the execution of the algorithm proceeds?

Question 5 (2%): Which global state S is discovered by the algorithm in this case?

PROBLEM 3.3 (17%)

Let us consider the computation in Figure 3, wherexandy are local variables of processes p1 and p2, respectively. At the beginning of the computation, both x and y are set to 0 (that is,x:= 0 and y:= 0).

Figure 3: Computation of the Distributed System

Question 1 (9%): Construct the lattice of global states for the computation.

Question 2 (4%): Describe the meaning of Def initely(φ) and P ossibly(φ), where φ is a generic predicate (for instance,φ =x > y).

Question 3 (2%): Check whether Def initely(x > y) isTrue or False in the computation.

In case of True, indicate the global states in which the property holds. In case of False, explain why the property does not hold.

Question 2 (2%): Check whether P ossibly(x−y=y)isTrue orFalse in the computation.

In case of True, indicate the global states in which the property holds. In case of False, explain why the property does not hold.

(6)

TOPIC 4 (32%): Distributed Algorithms

PROBLEM 4.1 (10%)

Let us consider the Ricart-Agrawala’s algorithm for distributed mutual exclusion. Starva- tion occurs when one process must wait indefinitely to enter its critical section even though other nodes are entering and exiting their own critical sections. Prove that starvation is impossible if processes run Ricart-Agrawala’s algorithm.

PROBLEM 4.2 (4%)

Let us consider the problem of distributed elections. Assuming that each process pi has a variableelectedi containing the identifier of the elected process (the variable is initially set to⊥, meaning null, not defined), define thesafety and liveness requirements that must be met during any particular run of a distributed elections algorithm.

PROBLEM 4.3 (10%)

FIFO ordered multicast can be achieved by means of sequence numbers. A key assumption of the basic FIFO multicast algorithm (sketched in Figure 4) is that processes are organized in non-overlapping groups.

Figure 4: Basic FIFO Multicast Algorithm

(7)

Question 2 (7%): Adapt the above FIFO multicast algorithm to work for overlapping groups of processes.

PROBLEM 4.4 (8%)

Consider the algorithm to solve consensus in a synchronous distributed system composed of n processes (Figure 5). The algorithm assumes that up to f of the n processes in the system exhibit crash failures. pi denotes a generic process belonging to a group g. The variable V aluesri holds the set of proposed values known to process pi at the beginning of round r, where 1≤r ≤f+ 1.

The algorithm is based on the following integrity definition: if the correct processes all proposed the same value, then any correct process in the decided state has chosen that value.

Now consider an application in which correct processes may propose different results, e.g. by running different algorithms to decide which action to take in a control system’s operation. Thus, it might be possible that there is no “same value” proposed by all the processes. Moreover, it might be possible that values cannot be ordered.

Figure 5: Consensus in a Synchronous System

Question 1 (5%): Suggest an appropriate modification to the integrity definition.

Question 2 (3%): Suggest an appropriate modification to the algorithm so that it satisfies the new integrity requirement (defined in Question 1).

End of the Exam

Referencer

RELATEREDE DOKUMENTER

maripaludis Mic1c10, ToF-SIMS and EDS images indicated that in the column incubated coupon the corrosion layer does not contain carbon (Figs. 6B and 9 B) whereas the corrosion

In this study, a national culture that is at the informal end of the formal-informal continuum is presumed to also influence how staff will treat guests in the hospitality

If Internet technology is to become a counterpart to the VANS-based health- care data network, it is primarily neces- sary for it to be possible to pass on the structured EDI

The adversary maintains a complete graph on n vertices, corresponding to the n elements that the algorithm may compare pairwise in queries.... Initially, all edges in the graph

During the 1970s, Danish mass media recurrently portrayed mass housing estates as signifiers of social problems in the otherwise increasingl affluent anish

Most specific to our sample, in 2006, there were about 40% of long-term individuals who after the termination of the subsidised contract in small firms were employed on

Statnett uses two markets for mFRR, accepting bids from production and consumption: the common Nordic energy activation market and a national capacity market. The purpose for using

The 2014 ICOMOS International Polar Heritage Committee Conference (IPHC) was held at the National Museum of Denmark in Copenhagen from 25 to 28 May.. The aim of the conference was