Parallel and distributed computer

please answer the attached file

College of Computing and Informatics
Instructions:
• You must submit two separate copies (one Word file and one PDF file) using the Assignment Template on
Blackboard via the allocated folder. These files must not be in compressed format.
• It is your responsibility to check and make sure that you have uploaded both the correct files.
• Zero mark will be given if you try to bypass the SafeAssign (e.g. misspell words, remove spaces between
words, hide characters, use different character sets, convert text into image or languages other than English
or any kind of manipulation).
• Email submission will not be accepted.
• You are advised to make your work clear and well-presented. This includes filling your information on the cover
page.
• You must use this template, failing which will result in zero mark.
• You MUST show all your work, and text must not be converted into an image, unless specified otherwise by
the question.
• Late submission will result in ZERO mark.
• The work should be your own, copying from students or other resources will result in ZERO mark.
• Use Times New Roman font for all your answers.
Question One
Pg. 01
Learning
Outcome(s):
Recognize the
fundamental
principles of
parallel and
distributed
processing,
parallel system
taxonomy, and
parallel system
performance
metrics
Question One
2 Marks
Sequential and Causal Consistency in Distributed Systems
1) Explain the fundamental difference between Sequential Consistency and
Causal Consistency in the context of parallel and distributed systems. Discuss
how these consistency models define the order in which operations appear to
be executed across multiple processes.
Sequential Consistency (SC) and Causal Consistency are two different
consistency models in parallel and distributed systems that define the order in which
operations appear for implementation in multiple processes.
Sequential Consistency is a system that ensures all operations from different
processes are executed in a single, sequential order, ensuring that the observed order
aligns with the global total order, even though the actual execution order may vary
across processes.
Causal Consistency is a concept that allows processes to observe the same order of
operations, ensuring that if an operation precedes another, all processes will be in
the same order. However, it may differ if operations are concurrent or unrelated,
affecting the overall order.
To summarize, Sequential Consistency enforces a global total order, while Causal
Consistency preserves causality between operations.
Pg. 02
Question One
2) Consider a simple distributed system with three processes (P1, P2, P3) that
perform arithmetic operations. Assume each process has a local variable to
store a numerical value, and they exchange messages to update these values
(e.g., add 1, multiply by 2, subtract 5, etc.). Design a scenario where the
difference between Sequential Consistency and Causal Consistency
becomes apparent. Provide a step-by-step explanation of the operations and
message exchanges, illustrating how the two consistency models would lead
to different outcomes.
The scenario demonstrates the distinction between Sequential
Consistency and Causal Consistency.
Considering the following distributed system scenario involving three
processes (P1, P2, and P3):
• At the beginning, a local variable with the “value 0” exists in every
process: P1 = 0, P2 = 0, P3 = 0.
First Step:
P1 performs an increment operation (add 1) on its local variable: P1= 1.
Second Step:
P1 sends a message to P2 with the updated value, and P2 receives the
message and updates its local variable accordingly: P2= 1.
Third Step:
P2 performs a multiplication operation (multiply by 2) on its local variable:
P2= 2.
Four Step:
P2 sends a message to P3 with the updated value, and P3 receives the
message and updates its local variable accordingly: P3= 2.
Fifth Step:
P3 performs a subtraction operation (subtract 5) on its local variable: P3= -3.
Pg. 03
Question One
By examining the outcomes under Sequential Consistency and Causal
Consistency:
Sequential Consistency:
Under Sequential Consistency, the order of operations observed by any
process should be consistent with a global total order.
In this scenario, the global total order would be:
P1 increment, P2 multiplication, P3 subtraction.
Thus, the final values under Sequential Consistency would be:
P1=1, P2= 2, P3= -3.
Causal Consistency:
Under Causal Consistency, the order of operations should preserve
causality.
In this scenario, the causal order would be:
P1 increment -> P2 multiplication -> P3 subtraction.
Thus, the final values under Causal Consistency would be:
P1: 1, P2: 2, P3: -3.
Sequential Consistency and Causal Consistency yield the same outcome in
this scenario, but their differences become evident when dealing with
concurrent or unrelated operations. Causal Consistency permits partial
ordering of unrelated operations actions, while Sequential Consistency
enforces strict global total order.
Question Two
Pg. 04
Learning
Outcome(s):
Recognize the
fundamental
principles of
parallel and
distributed
processing,
parallel system
taxonomy, and
parallel system
performance
metrics
Question Two
3 Marks
Analyzing Parallel Bubble Sort Performance
Consider the problem of parallel Bubble sort. The serial time for Bubble sort is
200 seconds, and the parallel time for an efficient parallelization using a parallel
Bubble sort algorithm is 60 seconds.
Calculate Speedup and Efficiency:
1) Calculate the speedup S achieved by the parallel implementation.
2) Assume that the number of processors is 6, calculate the efficiency E
of the parallel implementation.
Analytical Questions:
3) Discuss the implications of the calculated speedup. What does a
speedup of 3.33 indicate about the efficiency of the parallel algorithm?
4) Explain how the concept of speedup differs from efficiency. In what
situations might a high speedup not necessarily imply high efficiency?
Optimization Scenario:
5) Suppose an optimization is applied to the parallel algorithm, reducing
the parallel time to 45 seconds. Recalculate the speedup and
efficiency with this improved parallel time. Discuss the impact of the
optimization on the performance metrics.
1- The speedup (S) of a system can be calculated using the formula:
S = Serial Time / Parallel Time.
The speedup (S):
Serial Time = 200 seconds
Parallel Time = 60 seconds
S = 200 / 60 = 3.33.
Question Two
Pg. 05
2- The Efficiency (E) of a system can be calculated using the formula:
E = Speedup / Number of Processors.
The Efficiency (E):
Number of Processors = 6
E = 3.33 / 6 = 0.5555.
3- The parallel algorithm is 3.33 times faster than the serial algorithm,
indicating a significant reduction in execution time. However, this does
not necessarily imply efficiency. The efficiency is 0.56, indicating that
each processor is utilized at 56% of its capacity. The speedup alone does
not determine the efficiency of the parallel algorithm. Therefore, the
efficiency of the parallel algorithm is not solely determined by its
speedup.
4- Speedup is the performance improvement achieved through parallelism,
comparing the execution time of a serial implementation to the execution
time of a parallel implementation. Efficiency measures the efficient
utilization of available resources in a parallel algorithm. High speedup
doesn’t necessarily mean high efficiency; efficiency may be low if the
parallel algorithm doesn’t efficiently utilize resources or if significant
overheads, such as high coordination and communication overheads,
reduce the efficiency of the parallel algorithm.
Question Three
Pg. 06
Learning
Outcome(s):
Design algorithms
using Dense
Matrix, Search
Question Three
3 Marks
Enhancing Distributed Systems with Caching and Replication
In the realm of parallel and distributed systems, the efficient management of
data is critical for performance optimization. Caching and replication are two
common strategies used to enhance data access and availability.
Algorithms for
Discrete
1) What are the essential alternatives for caching and replication in distributed
Optimization
systems?
2) Discuss the advantages and disadvantages of each alternative.
3) Explain how these alternatives contribute to improving system performance,
fault tolerance, and overall scalability.
Problems.