COMP212-DISTRIBUTED SYSTEMS EXAM
QUESTIONS WITH 100%VERIFIED
ANSWERS
What is a distributed system? - ✔✔A collection of independent computers that appears to its
users as a single coherent system
What are some main goals of distributed systems? - ✔✔Transparency
Openness
Reliability
Performance
Scalability
Connect users & resources
What is a transparent distributed system? - ✔✔It appears to its users as if it were only a single
computer system
What is a scalable distributed system? - ✔✔One that is capable of growing
List some graph topologies - ✔✔Ring
Tree
Complete network
What is an undirected network - ✔✔A network that you can go in either direction down along
an edge
What is a directed network - ✔✔A network that you can only go in the specified direction
down along an edge
,What are the 4 steps of a synchronous round? - ✔✔1. all nodes read incoming messages
2. all nodes update their state
3. all nodes generate new messages and put them in transit
4. all messages are transmitted over the channels and the next round begins
Which step(s) of a synchronous round are handled locally? - ✔✔1, 2, 3
Which step(s) of a synchronous round are handled by the network? - ✔✔4
What are two algorithms used for leader election in directed ring networks? - ✔✔LCR
HS
What are a few ways we measure the performance of a distributed algorithm? - ✔✔Time
Complexity (#rounds required)
Space Complexity (memory used)
Communication Complexity ( total #messages transmitted, size of messages)
What is the time complexity of LCR? - ✔✔n rounds
What is the worst case communication complexity of LCR? - ✔✔O(n^2) messages
What algorithm can we use to elect a leader in a general network? - ✔✔Flooding/FloodMax
How does LCR work? - ✔✔all nodes send their initial id clockwise
upon receiving an incoming id, compare it to your own
-if incomingID > ownID, forward incomingID
-if incomingID < ownID, discard incomingID
-if incomingID = ownID, declare self leader
, What is the diameter of a network - ✔✔the greatest shortest path between nodes
How does FloodMax work? - ✔✔diameter = D
all processors store the greatest id that they have seen
in every round send the greatest id to all out-neighbours
after D rounds compare the greatest stored id and own id, if the are equal declare self the leader
What is the time complexity of FloodMax? - ✔✔O(D+1)
What is the communication complexity of FloodMax? - ✔✔D*m
m is the number of direct links in the network
What type of protocol is IP? - ✔✔network protocol
What type of protocol is TCP? - ✔✔transport protocol
What type of protocol is HTTP? - ✔✔application protocol
What type of protocol is FTP - ✔✔application protocol
What are the main properties of TCP? - ✔✔connection oriented
reliable but slow
QUESTIONS WITH 100%VERIFIED
ANSWERS
What is a distributed system? - ✔✔A collection of independent computers that appears to its
users as a single coherent system
What are some main goals of distributed systems? - ✔✔Transparency
Openness
Reliability
Performance
Scalability
Connect users & resources
What is a transparent distributed system? - ✔✔It appears to its users as if it were only a single
computer system
What is a scalable distributed system? - ✔✔One that is capable of growing
List some graph topologies - ✔✔Ring
Tree
Complete network
What is an undirected network - ✔✔A network that you can go in either direction down along
an edge
What is a directed network - ✔✔A network that you can only go in the specified direction
down along an edge
,What are the 4 steps of a synchronous round? - ✔✔1. all nodes read incoming messages
2. all nodes update their state
3. all nodes generate new messages and put them in transit
4. all messages are transmitted over the channels and the next round begins
Which step(s) of a synchronous round are handled locally? - ✔✔1, 2, 3
Which step(s) of a synchronous round are handled by the network? - ✔✔4
What are two algorithms used for leader election in directed ring networks? - ✔✔LCR
HS
What are a few ways we measure the performance of a distributed algorithm? - ✔✔Time
Complexity (#rounds required)
Space Complexity (memory used)
Communication Complexity ( total #messages transmitted, size of messages)
What is the time complexity of LCR? - ✔✔n rounds
What is the worst case communication complexity of LCR? - ✔✔O(n^2) messages
What algorithm can we use to elect a leader in a general network? - ✔✔Flooding/FloodMax
How does LCR work? - ✔✔all nodes send their initial id clockwise
upon receiving an incoming id, compare it to your own
-if incomingID > ownID, forward incomingID
-if incomingID < ownID, discard incomingID
-if incomingID = ownID, declare self leader
, What is the diameter of a network - ✔✔the greatest shortest path between nodes
How does FloodMax work? - ✔✔diameter = D
all processors store the greatest id that they have seen
in every round send the greatest id to all out-neighbours
after D rounds compare the greatest stored id and own id, if the are equal declare self the leader
What is the time complexity of FloodMax? - ✔✔O(D+1)
What is the communication complexity of FloodMax? - ✔✔D*m
m is the number of direct links in the network
What type of protocol is IP? - ✔✔network protocol
What type of protocol is TCP? - ✔✔transport protocol
What type of protocol is HTTP? - ✔✔application protocol
What type of protocol is FTP - ✔✔application protocol
What are the main properties of TCP? - ✔✔connection oriented
reliable but slow
