COMP 212-DISTRIBUTED SYSTEMS EXAM
QUESTIONS WITH 100%VERIFIED
ANSWERS
Distributed System - ✔✔Collection of independent computers that appears to its users as a
single coherent system
Main goals of a distributed System - ✔✔1. Easy connection between users/resources
2. Transparency
3. Openness
4. Reliability
5. Performance
6. Scalability
Transparent Distributed system - ✔✔A distributed system that appears to its users as if it were
only a single computer system
Scalable Distributed System - ✔✔One that is capable of growing in size, the maximum
distance between its participants (geographical), and the number of administrative domains in it
Processors - ✔✔Computing entities.
Usually execute the same algorithm
Networks - ✔✔Connects processors.
EX. ring, tree, complete network
Processors communicate by interchanging messages through the links of the network
,What should happen in a round? - ✔✔1. read incoming messages
2. Update states
3. Generate new messages, put them in transit
4. messages should be transmitted (Could also come first)
What are some distributed tasks/problems? - ✔✔Message sending, leader election
Distributed algorithm - ✔✔1. executed by all processors
2. May have some input (ids, other info)and have some initial state
3. Every processor reads incoming messages/updates states/generates out going messages
4. Network delivers the messages
5. Next round begins
6. Processors produce some output
Informal description (of an algorithm) - ✔✔Gives the main idea in verbal form
Must be clear and concise to provide an accurate highlight/sketch of how the algorithm works
Psuedocode - ✔✔Informal code
A piece of code to be re-executed by all processors in every round
What should be taken into consideration when devising an algorithm? - ✔✔1. Convince that it
is correct
2. Analyze its performance
Correctness - ✔✔Proof that the algorithm does as expected
, Performance - ✔✔Measured by 3 things:
1. Time Complexity
2. Space complexity
3. Communication Complexity
Time complexity - ✔✔measures the time it takes for an algorithm to execute (ex # rounds
required)
Space complexity - ✔✔A measurement of how much memory is used by the processors
during the runtime of the algorithms
Communication Complexity - ✔✔A measurement of message size and quantities during the
execution of an algorithm
How is a spanning tree of a network given? - ✔✔• Network G = (V, E)
• Eʹ ⊆ E specifies a spanning tree T = (V, Eʹ)
• Root: u0 (leader)
• Processors know T in a distributed way
• Each u "i" knows: a parent "i", a set children
Time complexity of spanning tree broadcasting - ✔✔Depth d of T
Communication complexity of spanning tree broadcasting - ✔✔n - 1 messages
Time complexity of spanning tree construction - ✔✔O(D) where D is the maximum distance
of a u "i" from u "0" in G
QUESTIONS WITH 100%VERIFIED
ANSWERS
Distributed System - ✔✔Collection of independent computers that appears to its users as a
single coherent system
Main goals of a distributed System - ✔✔1. Easy connection between users/resources
2. Transparency
3. Openness
4. Reliability
5. Performance
6. Scalability
Transparent Distributed system - ✔✔A distributed system that appears to its users as if it were
only a single computer system
Scalable Distributed System - ✔✔One that is capable of growing in size, the maximum
distance between its participants (geographical), and the number of administrative domains in it
Processors - ✔✔Computing entities.
Usually execute the same algorithm
Networks - ✔✔Connects processors.
EX. ring, tree, complete network
Processors communicate by interchanging messages through the links of the network
,What should happen in a round? - ✔✔1. read incoming messages
2. Update states
3. Generate new messages, put them in transit
4. messages should be transmitted (Could also come first)
What are some distributed tasks/problems? - ✔✔Message sending, leader election
Distributed algorithm - ✔✔1. executed by all processors
2. May have some input (ids, other info)and have some initial state
3. Every processor reads incoming messages/updates states/generates out going messages
4. Network delivers the messages
5. Next round begins
6. Processors produce some output
Informal description (of an algorithm) - ✔✔Gives the main idea in verbal form
Must be clear and concise to provide an accurate highlight/sketch of how the algorithm works
Psuedocode - ✔✔Informal code
A piece of code to be re-executed by all processors in every round
What should be taken into consideration when devising an algorithm? - ✔✔1. Convince that it
is correct
2. Analyze its performance
Correctness - ✔✔Proof that the algorithm does as expected
, Performance - ✔✔Measured by 3 things:
1. Time Complexity
2. Space complexity
3. Communication Complexity
Time complexity - ✔✔measures the time it takes for an algorithm to execute (ex # rounds
required)
Space complexity - ✔✔A measurement of how much memory is used by the processors
during the runtime of the algorithms
Communication Complexity - ✔✔A measurement of message size and quantities during the
execution of an algorithm
How is a spanning tree of a network given? - ✔✔• Network G = (V, E)
• Eʹ ⊆ E specifies a spanning tree T = (V, Eʹ)
• Root: u0 (leader)
• Processors know T in a distributed way
• Each u "i" knows: a parent "i", a set children
Time complexity of spanning tree broadcasting - ✔✔Depth d of T
Communication complexity of spanning tree broadcasting - ✔✔n - 1 messages
Time complexity of spanning tree construction - ✔✔O(D) where D is the maximum distance
of a u "i" from u "0" in G
