Distributed Computing Principles Algorithms And Systems 1st Edition Ajay D. Kshemkalyani, Mukesh Singhal - Solutions

4. Prove that the predicate detection problem is NP-complete.(Hint: Show a reduction from the satisfiability (SAT) problem.)
3. Somewhat similar to the earlier problem, we now need to show a stronger property for linear predicates. Using the standard notation, let Cuts(φ) denote the set of cuts satisfying φ. Prove the following. “Cuts(φ) is closed under intersection if and only if φ is linear.”
2. A conjunctive predicate φ = ∧i∈Nφi, where φi is a predicate defined on variables local to process Pi.In a distributed execution (E,≺), let First_Cut(φ) be denote the earliest or smallest consistent cut in which the global conjunctive predicate φ becomes true.Recall that in different
Show by examples that the staircase configuration among sites is preserved in Singhal’s dynamic mutual exclusion algorithm when two or more sites request the CS concurrently and have executed the CSs.
Show that in Lamport’s algorithm the critical section is accessed in the increasing order of timestamps.
Mutual exclusion can be achieved using the following simple method in a distributed system(called the “centralized" mutual exclusion algorithm):To access the shared resource, a site sends the request to the site that contains the resource.This site executes the requests using any classical
Show that in Ricart-Agrawala algorithm the critical section is accessed in the increasing order of timestamps. Does the same hold in Maekawa’s algorithm?
What is the purpose of a REPLY message in Lamport’s algorithm? Note that it is not necessary that a site must always return a REPLY message in response to a REQUEST message.State the condition under which a site does not have to return REPLY message. Also, give the new message complexity per
Show that in Lamport’s algorithm if a site Si is executing the critical section, then Si’s request need not be at the top of the request_queue at another site Sj . Is this still true when there are no messages in transit?
In Lamport’s algorithm Condition L1 can hold concurrently at several sites. Then why do we need this condition for guaranteeing mutual exclusion.
Consider the following simple method to enforce mutual exclusion: All sites are arranged in a logical ring fashion and a unique token circulates around the ring hopping from a site to another site. When a site needs to executes its CS, it waits for the token, grabs the token, executes the CS, and
5. Consider the matrix clocks given in Figure 8.10. At any point in time after the execution of atomic steps MC0, MC1, MC2, or MC3, what is the minimum number of entries among the n2 entries of Clki that are guaranteed to be replicas of other entries in Clki? Identify the exact set(s) of elements
4. In Theorem 9, assume that there exists an upper bound on message transmissiontimes.Which (if any) variant of concurrent common knowledge can hold in the system? please state your assumptions clearly to justify your reasoning used in your answer.
3. In a failure-free asynchronous message-passing system of n processes, process Pi learns a fact φ.(a) Devise simple noninhibitory protocols using a logical ring along which to pass control messages to achieve the following, and justify your answers. Use timing diagrams to illustrate your
2. There are two black hats and two white hats. One of these hats is hidden away and the color of this hat is not known to anybody. The remaining three hats are placed on the heads of three persons A, B, and C in such a way that none of the persons knows the color of the hat placed on his/her head.
1. In the Muddy Children puzzle (Section 8.1), if = “At most k children have mud on the forehead,” will the muddy children be able to identify themselves? If yes, in how many rounds of questioning? If not, why not? Analyze this scenario in detail.
5. Design an efficient termination detection algorithm for a system where computation at a process is instantaneous (that is, all proceses are always in the idle state.)
4. Design an efficient termination detection algorithm for a system where communication delay is zero.
3. Termination detection algorithms assume that an idle process can only be activated on the reception of a message. Consider a system where an idle process can become active spontaneously without receiving a message. Do you think a termination detection algorithm can be designed for such a system?
2. Design a termination detection algorithm that is based on the concept of weight throwing and is tolerant to message losses. Assume that processe do not crash.
1. Haung’s termination detection algorithm could be redesigned using a counter to avoid the need of splitting weights. Present an algorithm for termination detection that uses counters instead of weights.
19. The algorithms for creating the propagation tree, the Steiner tree, and the delay-bounded Steiner tree are centralized. Identify the exact challenges in making these algorithms distributed.
18. Design a graph for which the CSTCD and CSTC heuristics yield different delay-bounded Steiner trees.
17. For the graph in Figure 6.28, compute the following spanning trees.(a) Steiner tree (based on the KMB heuristic)(b) Delay-bounded Steiner (heuristic CSTCD), with a delay bound of 8 units.(c) Delay-bounded Steiner (heuristic CSTC), with a delay bound of 8 units.
16. Prove that the propagation tree for a given set of groups is not unique.
15. Give the (centralized) algorithm for creating a propagation tree, for any set of groups.
14. Consider the Reverse Path Forwarding algorithm of Figure 6.26 for doing a multicast (a) Modify the code to perform pruning of the multicast tree.(b) Now modify the code of (1) to also deal with dynamic changes to the network topology(use the algorithms in Module 2).(c) Now modify the code to
13. In the example of Figure 6.22, draw the propagation tree that results if: hCEi were considered before hBCDi as a child of hABCi.
12. For multicast algorithms, show the following.(a) Privilege-based multicast algorithms provide (i) causal ordering if closed groups are assumed, and (ii) total ordering.(b) Moving sequencer algorithms, which work with open groups, provide total ordering but not causal ordering.(c) Fixed
11. For the multicast algorithm based on propagation trees, answer the following.(a) About a tight upper bound on the number of multicast groups.(b) About a tight upper bound on the number of meta-groups of the multicast groups.(c) Examine and justify in detail, the impact (to the propagation tree)
10. Design a (centralized) algorithm to create a propagation tree satisfying the properties given in Section 6.8.
9. Assume that all messages are being broadcast. Justify your answers to each of the following.(a) Modify the causal message ordering algorithm in Figure 6.13 so that processes use only two vectors of size n, rather than the n × n array.(b) Is it possible to implement total order using a vector of
8. Show the following containment relationships between causally ordered and totally ordered executions. (Hint: You may use Figure 6.12.)(a) Show that a causally ordered multicast need not be a total order multicast.(b) Show that a total order multicast need not be a causal order multicast.
7. The algorithm to implement synchronous order by scheduling messages, as given in Figure 6.10, uses process identifiers to break cyclic waits.(a) Analyze the fairness of this algorithm.(b) If the algorithm is not fair, suggest some ways to make it fair.(c) Will the use of rotating logical
6. Rewrite the spanning tree algorithm of Figure 5.6 using CSP-like notation. You can assume a wildcard operator in a receive call to specify that any sender can be matched.
5. Synchronous systems were defined in Chapter 5. Synchronous send and receive primitives were also introduced in Chapter 1. Synchronous executions were defined formally in Definition 13.These concepts are closely related. Explain carefully the differences and relationships between:(i) a
4. Show that a non-CO execution must have a crown of size 2.
3. Give a linear time algorithm to determine whether an A-execution (E,≺) is RSC.Hint: Use the definition of a crown and perform a topological sort on the messages using the→֒ relation.
2. Draw the directed graph (T , →֒) for each of the executions in Figures 6.2, 6.3, and 6.5.
1. (Characterizing causal ordering)(a) Prove that the CO property (Definition 8) and the Message Order property (Definition 10) characterize an identical class of executions.(b) Prove that the CO property (Definition 8) and the Empty Interval property (Definition 11) characterize an identical class

Showing 600 - 700 of 640

1
2
3
4
5
6
7

Step by Step Answers