Distributed Computing Quiz 2 - BITS WILP - Mtec Software Systems - 2017

Distributed Computing - Quiz 2

BITS WILP - Mtec Software Systems - 2017 

1. The number of messages exchanged by the Chandy–Misra–Haas algorithm for the AND model in order to detect a deadlock in a distributed system consisting of n sites and m processes is

Select one:
mn
(m(n−1))/2
(n(m−1))/2
(mn)/2

Ans: (m(n−1))/2

2. The ASSIGN_PRIVILEGE routine is executed by

Select one:
Raymond’s Tree-Based Algorithm
Chandy-Misra-Haas algorithm
Maekawa's algorithm
Lamport's algorithm

Ans: Raymond’s Tree-Based Algorithm

3. Which of the following is not an approach for implementing mutual exclusion in distributed systems?

Select one:
quorum-based approach
token-based approach
non-token-based approach
causal-ordering based approach

Ans: causal-ordering based approach

4. For a spanning tree having n nodes, a broadcast procedure requires

Select one:
2n messages
n2 messages
(n -  1) messages
n messages

Ans: (n -  1) messages

5. Which of the following local variables is not used in Synchronous Single-Initiator Spanning Tree algorithm using flooding?

Select one:
child
depth
parent
visited

Ans: child

6. For the single-resource model, maximum out-degree of a node in a WFG can be

Select one:
exactly 2
more than 1
any positive number
at most 1

Ans: at most 1

7. The termination criterion for the Asynchronous Single-Initiator Spanning Tree Algorithm using flooding is

Select one:
(Children ∪ Unrelated) = (Neighbors \ {parent})
Children = Neighbors
(Neighbors ∪ Unrelated) = Children
(Children ∪ Unrelated) = Neighbors

Ans: (Children ∪ Unrelated) = (Neighbors \ {parent})

8. In Lamport's algorithm for implementing distributed mutual exclusion, a site that wants to enter the critical section sends REQUEST messages to

Select one:
a subset of all the sites
all the other sites
only a single specific site
a predesignated leader site

Ans: all the other sites

9. The type of communication used in the Birman-Schiper-Stephenson protocol is

Select one:
convergecast
unicast
multicast
broadcast

Ans: broadcast

10. For a distributed system consisting of k processes, Raynal–Schiper–Toueg algorithm uses SENT arrays each of size

Select one:
k2
2k
k
k x k

Ans: k x k

11. In a distributed system, when a process sends a message to a subset of the processes then the type of communication is called

Select one:
multicasting
convergecasting
unicasting
broadcasting

Ans: multicasting

12. For a distributed system having K sites, the number of messages required by Lamport's algorithm for implementing distributed mutual exclusion per critical section invocation is

Select one:
K - 1
K
2(K - 1)
3(K - 1)

Ans: 3(K - 1)

13. The Chandy–Misra–Haas algorithm for the OR model uses

Select one:
request and response messages
probe messages
inquire messages
query and reply messages

Ans: query and reply messages

14. The synchronization delay for the Ricart–Agrawala algorithm is equal to

Select one:
twice the average message delay
thrice the average message delay
the average message delay
half of the average message delay

Ans: the average message delay

15. Liveness property with regard to causal ordering of messages states that

Select one:
a message that a process decides to send must eventually be sent
a message that arrives at a process must eventually be delivered to the process
a message that is in transit must eventually reach the destination process
a message that is lost during transmission must eventually be retransmitted

Ans: a message that arrives at a process must eventually be delivered to the process

16. For the Asynchronous Single-Initiator Spanning Tree Algorithm using flooding, ACCEPT messages are sent along

Select one:
the back edges
the cross edges
the tree edges
all edges

Ans: the tree edges

17. How many types of messages are used by the Asynchronous Single-Initiator Spanning Tree algorithm using flooding?

Select one:
2
3
5
4

Ans: 3

18. In a distributed system consisting of x processes, the space requirement at each process for the Raynal–Schiper–Toueg algorithm is

Select one:
O(x2) integers
O(x3) integers
O(x) integers
O(x4) integers

Ans: O(x2) integers

19. The system throughput for a distributed mutual exclusion algorithm is defined as

Select one:
the rate at which the system executes requests for the critical section
the rate at which the system sends messages to enable a process to enter the critical section
the rate at which the system receives requests for the critical section
the rate at which a process in the system sends requests for entering the critical section

Ans: the rate at which the system executes requests for the critical section

20. The safety property in context of distributed mutual exclusion algorithms states that

Select one:
at any instant, atmost a certain number of processes can execute the critical section
at any instant, atmost 2 processes can execute the critical section
at any instant, some process should be executing the critical section
at any instant, only one process can execute the critical section

Ans: at any instant, only one process can execute the critical section

21. For handling deadlocks, Maekawa’s algorithm uses the following types of messages

Select one:
REQUEST, FAILED, INQUIRE
REQUEST, REPLY, INQUIRE
FAILED, INQUIRE, YIELD
REQUEST, INQUIRE, YIELD

Ans: FAILED, INQUIRE, YIELD

22. The local space complexity at a node for the Synchronous Single-Initiator Spanning Tree algorithm using flooding is of the order of

Select one:
the degree of edge incidence
the sum of the diameter and the degree of edge incidence
the number of edges of the graph
the product of the number of edges and the number of nodes of the graph

Ans: the degree of edge incidence

23. For which of the algorithms for implementing distributed mutual exclusion, each process maintains a request-deferred array?

Select one:
Maekawa’s algorithm
Lamport's algorithm
Ricart–Agrawala algorithm
Suzuki–Kasami’s broadcast algorithm

Ans: Ricart–Agrawala algorithm

24. The number of rounds that are executed in the Synchronous Single-Initiator Spanning Tree algorithm using flooding is equal to

Select one:
the number of edges in the graph
the length of the longest path in the graph
the diameter of the graph
the number of nodes in the graph

Ans: the diameter of the graph

25. Which of the following type of multicast algorithm uses a token?

Select one:
communication history-based algorithm
moving sequencer algorithm
fixed sequencer algorithm
destination agreement algorithm

Ans: moving sequencer algorithm