Name of the University : Mahatma Gandhi University
Department : Information Technology
Degree : M.Tech
Subject Code/Name : MITNE 204/Distributed Algorithms
Sem : II
Website : mgu.ac.in
Document Type : Model Question Paper
Download Model/Sample Question Paper :
I : https://www.pdfquestion.in/uploads/mgu.ac.in/5309-1-MITNE%20204%20Distributed%20Algorithms%20-set1.doc
II : https://www.pdfquestion.in/uploads/mgu.ac.in/5309-2-MITNE%20204%20Distributed%20Algorithms%20-set2.doc
Distributed Algorithms Question Paper :
M.TECH. Degree Examination :
Model Question Paper – II :
Second Semester :
Related : MGU MITNE203 Wireless & Mobile Networks M.Tech Model Question Paper : www.pdfquestion.in/5308.html
Branch: Information Technology
Specialization: Network Engineering
(Regular – 2011 Admission on wards)
Time: Three hours
Maximum: 100 Marks
1. Consider an undirected network of N> 3 processes P0,…………….Pn-1, where P1,…… ………..Pn-1 form a ring and P0 has a channel to all other processes. Give an execution of the echo algorithm on this network, with P0 as initiator that takes N time units to complete. Assuming that a message takes at most one time unit. (25 marks)
OR
2. Run the Fire Wire leader election protocol on an acyclic undirected network of three processes. Give a scenario in which a leader is elected after an occurrence of root contention. (25 marks)
3. Consider the Itai-Rodeh ring size algorithm. Argue why upon message termination, ESTp is the same at all processes ‘p’. (25 marks)
OR
4. The requirement of strong accuracy is stronger than the requirement that processes that never crash are never suspected. Give an example of a failure pattern and a failure detector history that satisfy this property, but which are not allowed in case of a strongly accurate failure detector. (25 marks)
5. Run Raymond’s mutual exclusion algorithm on the graph below. Initially node 1 holds the token. Give a scenario in which first node 5, then node 4, and then node 2 requests the token, but they receive the token in the opposite order. (25 marks)
OR
6. In the t-Byzantine robust synchronizer of Lamport and Melliar – Smith, a correct process p accepts a local clock value of another process q if it differs no more than d from its own clock value, at the moment of synchronization. Explain in detail why that synchronizer has precision 3t/N d versus precision 2t/N d of the Mahaney –Schneider synchronizer. (25 marks)
7. Given three processes P0, P1 and P2 that are all connected to each other. Let leader0 = leader1=leader2=3; father0 =1, father1=2 and father2 = 0; dist0 =1, dist1 =0 and dist2= 2. Describe a scenario of the Afek-Kutten-Yung self stabilizing leader election algorithm, in which eventually P2 is elected as leader. (25 marks)
OR
8. Consider a processor with one periodic task(1,3,1),starts at time 1,period 3,execution time 1.Suppose sporadic jobs S1,S2,S3 and S4 arrive at times 0,1,3 and 6,with execution times 1,3,1 and 2,and with deadlines 1,12,7 and 14 respectively. Which of them pass the acceptance test for sporadic jobs? (25 marks)
M.Tech. Degree Examination :
Model Question Paper – I : Second Semester
Branch : Information Technology
Specialization : Network Engineering
MITNE 204 : Distributed Algorithms (Regular – 2011 Admission on wards)
Time : Three hours
Maximum : 100 Marks
1. a) Describe Synchronous Distributed computing systems. (10 marks)
b) How to an elect a leader in a network? Explain. (15 marks)
OR
2. a) Give working principle of Breadth –First search algorithm. (10 marks)
b) Explain the Bellman Ford routing algorithm with an Ex? State its drawbacks. (15 marks)
3. a) Discuss Leader election in a Synchronous ring. (10 marks)
b) Explain about Distributed consensus with link failures and Process failures. (15 marks)
OR
4. Write a note on :
i. LCR algorithm
ii. HS algorithm
iii. Time-slice algorithm
iv. Variable speeds algorithm
v. LubyMIS algorithm. (25 marks)
5. Discuss Peterson Leader election algorithm. (25 marks)
6. Write a note on :
i. Asynchronous Distributed computing systems.
ii. Local and Safe Synchronizers. (25 marks)
7. a) Write short notes on ‘Mutual Exclusion. (10 marks)
b) Briefly explain Symmetric Dining Philosophers Algorithms. (15 marks)
OR
8. Write a note on :
i. Dijkstra’s Mutual Exclusion Algorithm.
ii. Right-Left Dining Philosophers Algorithm
Modern Digital Communication Techniques :
1 a) Explain the following terms :
i. Information and Information rate.
ii. Entropy
iii. Shannon’s theorem
iv. Channel capacity (10 marks)
b) Define and explain various multiplexing techniques used in communication systems. (15 marks)
OR
2 a) Describe the scalar and vector communication over memory less channel. (15 marks)
b) Explain :
i. Shannon Hartley capacity theorem
ii. Shannon limit. (10 marks)