2 part ii advanced problem 4 9 marks 1 5 pages problem statement you h
2 Part II: Advanced
Problem 4 (9 marks, 1.5 pages). Problem Statement: You have two servers, X and Y,
each containing a database of n records, where each record is quite large (m bits).
Occasionally, a record may be updated on one server and not the other. To ensure both
servers have identical databases, they need to synchronize their data. During
synchronization, they exchange data in multiple rounds of communication.
Existing Algorithm: The simplest way to synchronize the data is for X to send its
entire database x to Y via the internet. Y then checks every record in x against its own
database y. If a record in x is the same as the corresponding record in y, Y does nothing.
If a record in x is different from the one in y, Y updates its database with the newer
record or sends the newer record to X. X, upon receiving a newer record from Y, updates
its own database.
Challenges with Existing Algorithm: While this method works, it consumes a lot
of bandwidth because it sends all n records over the network.
Goal: Your task is to design a more efficient synchronization algorithm that
minimizes communication complexity (sending data) and computation complexity
(calculating hash values). The key is to use cryptographic hash functions, which take
data as input and produce a fixed-size string (hash) as output. These hash functions are
collision-resistant, meaning it's hard to find two different inputs that produce the same
a) Overview (2 marks): Explain how your algorithm works, why it's a better
solution, and what the communication and computation complexities are.
b) Detailed Description (3 marks): Provide a detailed description of the main
steps of your algorithm, specifying what X and Y do to synchronize the two databases.
You can use pseudocode for this. The pseudocode format is not essential; clarity is key.
c) Demonstration (2 marks): Illustrate how your algorithm works with a small
example, like when n = 8.
d) Analysis (2 marks): State the communication and computation complexities of
your algorithm and explain why it has these complexities. The input size is (n, m).
The given marks are maximum possible for the parts. Your actual marks depend on
how efficient your algorithm is (regarding the communication complexity (major
criteria) AND the computation complexity) and also how well it is presented. A correct
and efficient but poorly written solution could still attract a low mark. An incorrect
solution will get a zero mark.
*The amount will be in form of wallet points that you can redeem to pay upto 10% of the price for any assignment. **Use of solution provided by us for unfair practice like cheating will result in action from our end which may include permanent termination of the defaulter’s account.Disclaimer:The website contains certain images which are not owned by the company/ website. Such images are used for indicative purposes only and is a third-party content. All credits go to its rightful owner including its copyright owner. It is also clarified that the use of any photograph on the website including the use of any photograph of any educational institute/ university is not intended to suggest any association, relationship, or sponsorship whatsoever between the company and the said educational institute/ university. Any such use is for representative purposes only and all intellectual property rights belong to the respective owners.