Trivial Synchronization Algorithm Assessment

Problem

 A database of n records, each of which has size m bits (we assume that m is large) is maintained at two different servers X and Y. As sometimes a record may get updated at one server and not at the other, the servers X and Y have to sync their (possibly different) databases x=(x1,...,xn) and y = (y1,...,yn) from time to time to make sure they are the same. At the synchronization time, the two servers exchange some data in one or several rounds of communications.

A trivial synchronization algorithm is as follows: X sends x via the internet to Y, which verifies every record of x against that of its database y; for each 1sis, ifx,y, then Y does nothing, otherwise, it will either update y, x, if x, is newer or send (i,y) - to X if its record is newer; upon receiving a pair (i,y), X updates x,y. We assume there is an efficient mechanism (which is not our focus) to decide which version of the record is newer (e.g., using a naming convention like ver-1.2.1 is newer than ver-1.2.0). While this solution works, it requires a huge bandwidth because at least n records have to be sent across the network.

Our goal is to design a more efficient protocol/algorithms using a tool called crypto- graphic hash function. A cryptographic hash function h() takes as input any piece of data x of any size and returns a fixed-size string h(x) (e.g., h(x) is of size 256 bits for SHA-256). Moreover, different from a non-cryptographic hash function (Week 11), they are collision-resistant, that is, it's hard to find two different inputs that hash to the same output. As a consequence, in practice, we can assume that if ab then h(a) h(b). For simplicity, we assume that the following assumptions hold.

1. At most one item is different between the two databases, that is, either x = y; for all i = 1,...,n, or there exists an index i such that x-y- and x = y; for all i #i".
2. The computation complexity is measured by the number of hashes required to be computed by both X and Y and also by the amount of data that are hashed. For instance, the trivial protocol described above requires no hash computation, and hence, the computation complexity is zero.
3. The communication complexity is measured by the number of hashes and the number of records communicated between X and Y. For instance, the trivial proto- col sends no hashes and n records, which is very expensive (a record is much larger than a hash).

Your task is to design a synchronisation algorithm that requires a small communi- cation complexity (most important) and also a reasonable computation complexity. More specifically, you need to include the following in your answer.

1. (Overview - 2 mark) An overview of how your algorithm works, why it solves the problem, and what are the communication and computation complexities.
2. (Detailed description-3 marks) A detailed description of the main steps of the algorithm, describing what X and Y do to sync the two databases. You could also write your description using a pseudocode. The goal is to guarantee that other peo- ple can understand clearly how the algorithm works. The format of the pseudocode is not important.

Are you struggling to keep up with the demands of your academic journey? Don't worry, we've got your back! Exam Question Bank is your trusted partner in achieving academic excellence for all kind of technical and non-technical subjects.

Our comprehensive range of academic services is designed to cater to students at every level. Whether you're a high school student, a college undergraduate, or pursuing advanced studies, we have the expertise and resources to support you.

To connect with expert and ask your query click here Exam Question Bank