1 Introduction

In scalable distributed systems like cloud computing systems [1, 5, 10, 11] and peer-to-peer (P2P) overlay networks [12, 15, 16, 19, 20], resource objects like files and databases are replicated in multiple computers in order to increase the performance, reliability, and availability. Multimedia objects in addition to simple objects like files are distributed in networks. Especially, multimedia objects are in nature autonomously distributed to computers through peer-to-peer communication like downloading in P2P overlay networks. There are many discussions on how to maintain the mutual consistency of multiple replicas of a simple object like a file [7]. There is at least one up-to-date replica in a quorum and a pair of a read quorum and a write quorum include at least one common replica in the QB protocols [2, 6, 9, 17, 18]. Up-to-date replicas in a quorum can be found in version counters [3]. Every replica in a write quorum is updated to be the newest one each time a write operation is issued. For a read operation, a newest replica o i in a read quorum is read. Then, every replica which is older than the newest replica o i is changed with the same state as the replica o i .

Multimedia objects are characterized in terms of quality of service (QoS) in addition to data structure. Hence, each replica o i of a multimedia object o is characterized in terms of parameters p 0,p 1,…,p l (l≥1) where the first parameter p 0 shows the data structure, i.e. subobjects and another parameter p k indicates a QoS parameter like frame rate (k=1,…,l). Compared with simple objects like files, a larger volume of data is transmitted in networks and manipulated in a multimedia object. Computation resource is spent to manipulate multimedia replicas in computers. Hence, it is critical to discuss how to reduce the overhead, especially processing overhead of each replica. The multimedia quorum-based (MQB) protocol is discussed to reduce the overhead in the papers [13, 14]. Here, replicas are partially ordered in the version vector 〈vc 0,vc 1,…,vc l 〉 of version counters. Each version counter vc k is used for each parameter p k (k=0,1,…,l). Each version counter vc k is incremented so as to be larger than the maximum value in a write quorum each time the parameter p k is updated. A replica with the maximum version vector is newest, i.e. up-to-date in each quorum.

In order to increase the performance of the MQB protocol, we propose a novel synchronization mechanism where the state of a replica is not always changed while the parameters are changed. Each parameter p k in a replica o i is read and written in a read operation r k and write operation w k(x), respectively.

There are enriching and impoverishing types of write operations [14]. Some new data not in a replica is added in an enriching operation. For example, a subobject is added to a replica. On the other hand, some data in a replica is deleted in an impoverishing operation. For example, a QoS parameter, say the number of colours is reduced. The newer state of a replica shown by the parameters can be obtained by reducing data in the physical state. Hence, we take the following approach:

  1. 1.

    In an enriching type of write operation w k(x), every replica is updated in a write quorum Q kw .

  2. 2.

    In an impoverishing type of write operation w k(x), the new value x of the parameter p k is just recorded but each replica o i is not updated in a write quorum Q kw .

The replica o i is materialized, i.e. physically updated to be up-to-date by changing the state with one shown by the parameters. If a read operation r k is issued to read the kth parameter p k of a replica, the parameter p k of an up-to-date replica in a read quorum Q kr is read. In a read operation r 0 to read the data structure parameter p 0, a replica o i is materialized and a whole physical state of the replica o i is read. We also discuss an MQB-RM (read materialization) protocol where every replica is updated after a transaction reads a newest replica in a read quorum.

In the MQB and MQB-RM protocols, the processing overhead of each replica o i can be reduced since every replica may not be written in a write quorum, just parameters are changed. In this paper, we evaluate the MQB and MQB-RM protocols compared with the QB protocol in terms of the processing overhead. We show the processing overhead of each replica can be reduced in the MQB protocol compared with the QB protocol.

In Sect. 2, we discuss enriching and impoverishing types of operations of multimedia objects. In Sect. 3, we present procedures for read and write operations in the MQB and MQB-RM protocols. In Sect. 4, we evaluate the MQB and MQB-RM protocols compared with the QB protocol.

2 Multimedia objects

2.1 Parameters

An object o is an encapsulation of data structure and operations for manipulating the data structure. A multimedia object o is characterized in terms of not only data structure parameter but also quality of service (QoS) parameters. An object is characterized in a tuple 〈p 0,p 1,…,p l 〉 of logical parameters. The first logical parameter p 0 stands for the data structure scheme which shows the part_of structure of subobjects. For example, an object o is composed of subobjects a, b, and c. Here, the logical parameter p 0 of the object o is 〈a,b,c〉. The other logical parameters p 1,…,p l indicate QoS parameters (l≥1). For example, the second logical parameter p 1 shows the frame rate. If the frame rate of an object o is 40 fps, the logical parameter p 1 of the object o is 40. Here, the object o is shown in a tuple 〈〈a,b,c〉,40〉 of the logical parameters p 0 and p 1. In this paper, we assume every subobject of an object o has the same QoS parameters for simplicity.

Let x and y be a pair of values to be taken by a logical parameter p k . If p k is a QoS parameter (k≥1), the value x is poorer than y (x≺y) if x<y. For example, the frame rate 20 fps is poorer than 40 fps (20≺40). For a data structure parameter p 0 (k=0), x is poorer than y (x≺y) iff every subobject of x is included in y (x⊂y). For example, an object is composed of three subobjects 〈a,b,c〉 and another object is composed of two subobjects 〈a,b〉. Here, 〈a,b〉 is poorer than 〈a,b,c〉. x⪯y iff x≺y or x=y. x is richer than y iff x≻y. If x⪯y, y includes additional data which is not in x.

An object o is replicated in multiple computers. Let o i be a replica of the object o (i=1,…,n). Each replica o i supports the same operations and parameters as the object o. Each replica o i is also composed of the same logical parameters 〈p 0,p 1,…,p l 〉 as the object o. Let o i .p k indicate a logical parameter p k of a replica o i .

2.2 Types of operations

Each operation op k is performed to manipulate a logical parameter p k of a replica o i . There are two types of operations, read (r k) and write (w k) on a logical parameter p k , i.e. op∈{r,w}. A transaction reads a logical parameter p k of a replica o i in a read operation r k (k≥1). A read operation r 0 is used to read the whole state of a replica o i denoted by the logical parameters 〈p 0,p 1,…,p l 〉.

In the write operation w k(x), the value x is overwritten to the logical parameter p k of the replica o i . For example, suppose a logical parameter p k shows the frame rate of a replica o i . In a write operation w k(20), the frame rate parameter p k of the replica o i is changed with 20 fps. Here, the physical state of the replica o i is changed so that the frame rate is 20 fps in a traditional write operation.

We consider two types of write operations w k(x) on a parameter p k of a replica o i in this paper:

  1. 1.

    Materialization type of write.

  2. 2.

    Unmaterialization type of write.

In one type of write operation w k(x), not only the logical parameter p k but also the physical state of the replica o i are changed. This type of write operation is referred to as materialization write which is a traditional write operation. In another type of write operation w k(x), only the logical parameter p k is changed although the physical state is not changed in the replica o i . This type of write operation is referred to as unmaterialization write. We here introduce a physical parameter s k which shows the value of the kth parameter of the physical state of a replica o i . A physical state of a replica o i means a state which is physically stored in a computer. Thus, a tuple 〈s 0,s 1,…,s l 〉 of the physical parameters shows the physical state of a replica o i . On the other hand, a tuple 〈p 0,p 1,…,p l 〉 of the logical parameters denotes a logical state of a replica o i which shows a current state but may be different from the physical state. If a materialization write operation w k(x) is performed on a replica o i , both the logical parameter p k and the physical parameter s k of the replica o i are changed with a new value x. That is, p k =s k in the replica o i . On the other hand, if an unmaterialization write w k(x) is performed on a replica o i , only the logical parameter p k is changed with a new value x but the physical parameter s k is not changed. The change of the physical parameter s k means that the physical state of a replica o i is changed.

A replica o i where p k =s k for every logical parameter p k is referred to as materialized. In an unmaterialized replica o i , p k ≠s k for some logical parameter p k . Here, an unmaterialized replica o i is referred to as materializable iff the logical parameter p k is equal to or poorer than the physical parameter s k (p k ⪯s k ) for every logical parameter p k . Suppose a replica o i is not materialized, i.e. p k ≠s k for some logical parameter p k which shows the frame rate. Suppose the logical parameter p k of a frame rate is 20 fps and the physical parameter s k is 40 fps. That is, the physical parameter s k is richer than the logical parameter p k (p k ⪯s k ). Here, we can obtain the current physical state of the replica o i just by decreasing the frame rate without obtaining additional data not in the physical state. That is, the replica o i is materializeable. On the other hand, if p k =40 fps and s k =20 fps, i.e. the logical parameter p k is poorer than the physical parameter s k (p k ≻s k ), the current physical state of the replica o i cannot be obtained without additional frame data which is not in the physical state of the replica o i .

For a pair of different logical QoS parameters p k and p h (k≠h), a read operation r k is compatible with a write operation w h and a write operation w k is also compatible with a write operation w h. A read operation r 0 conflicts with a write operation w k of every logical parameter p k (k≥0) since the whole state of the replica o i is read in a read operation r 0. Let O be a set of replicas of an object o in a system S. Let Q k,op (⊆O) shows a quorum of replicas where an operation op k on a parameter p k is performed. For every pair of operations \(op_{1}^{k}\) and \(op_{2}^{k}\), if \(op_{1}^{h}\) and \(op_{2}^{k}\) conflict with one another, \(Q_{k,op_{1}} \cap Q_{h,op_{2}} \neq\phi\) and \(Q_{k,op_{1}} \cup Q_{h,op_{2}} = O\).

Write operations are further classified into the following types [13, 14] with respect to whether some data is added or removed on a replica o i :

  1. 1.

    Enriching type of write.

  2. 2.

    Impoverishing type of write.

In an enriching type of write operation w k(x), some data not in a replica o i is required to be added to the replica o i . For example, colour data has to be added to a monochromatic replica to change with a coloured replica. That is, the value x is richer than the physical parameter s k of a replica o i (x≻s k ). On the other hand, a replica o i can be updated just by removing data in the replica o i in an impoverishing type of write operation w k(x). That is, x⪯s k . For example, a coloured replica can be changed with a monochromatic one just by removing the colour data.

3 Multimedia quorum-based (MQB) protocol

3.1 Parameters

Let O be a set {o 1,…,o n } of replicas of a multimedia object o in a system S. Each replica o i is characterized in terms of logical parameters 〈p 0,p 1,…,p l 〉 (l≥1). The first logical parameter p 0 stands for the data structure of the replica o i which shows a part_of relation of subobjects. For example, a replica o i is composed of three subobjects a, b, and c. Here, the logical parameter p 0 is a tuple 〈a,b,c〉 of the subobjects in the replica o i . The other logical parameters p 1,…,p l show QoS parameters. For each logical parameter p k , there are a pair of operations r k and w k to read and write the parameter p k of a replica o i , respectively (k=0,1,…,l). For example, the colour parameter p 1 takes one of values; fc (fully coloured), gs (gray-scaled), and mc (monochromatic). The parameter p 2 is a QoS parameter which shows the frame rate, e.g. 40 fps. Here, suppose a replica o i is composed of fully coloured movie subobjects a, b, and c with frame rate 40 fps. A logical state of the replica o i is given in a tuple 〈〈a,b,c〉,fc,40〉 of logical parameters, where p 0=〈a,b,c〉, p 1=fc, and p 2=40. In the write operation w 0(x), a subobject x is deleted, added, or modified. For example, suppose the subobject c in the replica o i is deleted in a delete operation w 0(c). The replica o i is changed with a new state 〈〈a,b〉,fc,40〉. A delete is an impoverishing type of write operation and add is an enriching type of write operation. Suppose a QoS parameter p 2 stands for frame rate. In the write operation w 2(20), the frame rate parameter p 2 of a replica o i is changed with 20 fps. This is an impoverishing write operation since 40⪰20. The replica o i is changed with a new state 〈〈a,b〉,fc,20〉.

Each replica o i is characterized in a tuple 〈s 0,s 1,…,s l 〉 of physical parameters in addition to the logical parameters 〈p 0,p 1,…,p l 〉. Initially, s k =p k for each parameter p k in a replica o i . A tuple 〈s 0,s 1,…,s l 〉 of the physical parameters shows a physical state of a replica o i which is really stored in a computer. Hence, each parameter s k is referred to as physical parameter of a replica o i .

On receipt of a write operation w k(x), the logical parameter p k of a replica o i is updated with a new value x. However, the physical state of the replica o i is not changed if w k is an impoverishing type of write operation in our approach to reducing the processing overhead. On the other hand, the physical state of the replica o i is changed in an enriching type of write operation, i.e. not only the logical parameter p k but also the physical parameter s k are updated. In an impoverishing type of write operation w k(x), the logical parameter p k and the version counter vc k are updated in a replica o i while the physical parameter s k is not updated. Thus, a tuple 〈p 0,p 1,…,p l 〉 of the logical parameters shows a current logical state of a replica o i . On the other hand, a tuple 〈s 0,s 1,…,s l 〉 of the physical parameters denotes a current physical state of the replica o i which is really stored in a computer.

If a physical parameter s k is the same as the logical parameter p k , the logical parameter p k is referred to as materialized. A tuple 〈p 0,p 1,…,p l 〉 of the logical parameters shows a newest state of a replica o i . The logical parameter p k is materialized in an enriching write operation w k while not materialized in an impoverishing type of write operation w k. If every logical parameter p k of a replica o i is materialized, the replica o i is referred to as materialized, where p k =s k for every logical parameter p k . It is noted the logical parameter p k is equal to or richer than the physical parameter s k in a replica o i (o i .p k ⪰o i .s k ) since the replica o i is materialized each time an enriching write operation w k is performed but is not materialized, just the logical parameter p k is changed in an impoverishing write operation.

Next, suppose a read operation r 0 is issued to a replica o i to read the logical data structure parameter p 0. A newest replica o i is first selected in a read quorum Q 0r and then is materialized. The whole state of the replica o i is read in the read operation r 0.

Let us consider a replica o i =〈〈a,b,c〉,fl,40〉 of a movie object o which is composed of three subobjects a, b, and c which are fully coloured with 40 fps. Here, the logical parameters 〈p 0,p 1,p 2〉 are the same as the physical parameters 〈s 0,s 1,s 2〉 in the replica o i . First, the frame rate parameter p 2 is changed with 20 fps. Then, the subobject c is deleted in a write operation w 0(c) which is also an impoverishing type. Here, the logical parameter p 0 of data structure is changed with 〈a,b〉. The physical parameters 〈s 0,s 1,s 2〉 are still 〈〈a,b,c〉,fl,40〉 while the logical parameters 〈p 0,p 1,p 2〉 are changed with 〈〈a,b〉,fl,20〉. The physical data structure parameter s 0=〈a,b.c〉 is richer than the logical parameter p 0=〈a,b〉 (s 0⪰p 0) and the QoS parameters p 2=40 fps is richer than s 2=20 fps (s 2⪯p 2). A tuple 〈〈a,b,c〉,fl,40〉 of the physical parameters indicates a current physical state of the replica o i . A tuple 〈〈a,b〉,fl,20〉 of the logical parameters denotes a current logical state of the replica o i to be changed. Here, the replica o i is not materialized. The physical state of a replica o i shown by the physical parameters 〈s 0,s 1,…,s l 〉 is older than the logical state denoted by the logical parameters 〈p 0,p 1,…,p l 〉 if 〈s 0,s 1,…,s l 〉≠〈p 0,p 1,…,p l 〉.

Suppose a replica o i is not materialized but each logical parameter p k can be richer than a physical parameter s k . There is a materialization procedure mat(o i ) by which the physical state of a replica o i is changed from 〈s 0,s 1,…,s l 〉 to the new state 〈p 0,p 1,…,p l 〉, i.e. the replica o i is materialized. Here, the physical state of the replica o i is really changed. Computation resources are spent to change the physical state of the replica o i , i.e. materialize the replica o i . For example, data in the replica o i is decoded and encoded. Hence, we try to reduce the number of materializations to be done in replicas in this paper. Then, the physical state 〈s 0,s 1,…,s l 〉 of the replica o i is changed with 〈p 0,p 1,…,p l 〉. For example, the physical state of a replica o i is 〈〈a,b,c〉,fc,40〉 which is composed of three subobjects a, b and c with QoS parameters p 1=fl and p 2=40 fps. A tuple of the logical parameters 〈p 0,p 1,p 2〉 of the replica o i is 〈〈b,c〉,fc,20〉. Here, the replica o i can be materialized to the physical state 〈〈a,b〉,fc,20〉 by removing the subobject c and decreasing the frame rate to 20 fps. Here, the physical parameters 〈s 0,s 1,s 2〉 get the same as the logical parameters 〈p 0,p 1,p 2〉=(〈〈b,c〉,fc,20〉), i.e. the replica o i is materialized.

3.2 Version vector

For each logical parameter p k , there is a version counter vc k [14]. Initially, the version counter vc k of each logical parameter p k is 0 in each replica o i . Let o i .vc k stand for the version counter vc k of a replica o i , respectively. o i .V shows a vector 〈vc 0,vc 1,…,vc l 〉 of the version counters in a replica o i . Suppose a transaction T issues an operation op k to manipulate the parameter p k in a quorum Q k,op . If a write operation w k(x) is performed on a replica o i , the version counter o i .vc k is incremented by one. Here, a replica o i is newer than a replica o j iff o i .V>o j .V. In a quorum Q k,op , a replica o i whose version counter vc k is maximum has the newest parameter p k . If a read operation r k is issued, the logical parameter p k of a newest replica in a read quorum Q kr is read.

3.3 Read and write procedures of QoS parameters

We discuss how to manipulate replicas in a quorum. We first consider a read operation r k and a write operation w k(x) for a logical QoS parameter p k (k=1,…,l). Here, the transaction T obtains the newest value of the logical parameter p k by the following procedure (refer to Fig. 1).

Fig. 1
figure 1

Read procedure r k

Full size image

[Read procedure of r k]

  1. 1.

    Find a newest replica o i in a read quorum Q kr whose version counter o i .vc k is maximum, i.e. o i .vc k =max(o j .vc k ∣o j ∈Q kr ). vc=o i .vc k .

  2. 2.

    Read the logical parameter o i .p k in the replica o i .

  3. 3.

    For every replica o j (j≠i) in the quorum Q kr , o j .p k =o i .p k and o j .vc k =vc.

The transaction T finds a replica o i which has the newest value of the logical parameter p k in the read quorum Q kr . That is, the replica o i has the largest version counter vc k in the quorum Q kr . Then, the transaction T reads the logical parameter p k of the replica o i .

Next, a transaction T issues a write operation w k(x) to write a value x in a QoS parameter p k of replicas in a write quorum Q kw (refer to Fig. 2).

Fig. 2
figure 2

Write procedure w k(x)

Full size image

[Write procedure of w k(x)]

  1. 1.

    Find a replica o i in a write quorum Q kw whose version counter o i .vc k is maximum, i.e. newest replica o i . vc=o i .vc k +1.

  2. 2.

    For every replica o j (≠o i ) in the quorum Q kw , the value x is written to the logical parameter p k of the replica o j and the version vector vc k is changed with the maximum value vc, i.e. o j .p k =x and o j .vc k =vc.

  3. 3.

    If w k(x) is an enriching type of write operation, i.e. the logical parameter p k is richer than the physical parameter s k (p k ≻s k ), every replica o j in the quorum Q kw is materialized by the materialization procedure mat(o j ). The physical state of the replica o i is changed with a new state shown by a tuple 〈p 0,p 1,…,p l 〉 of the logical parameters. Now, the physical state of the replica o i is up-to-date.

It is noted that the new parameter value x is written to the logical parameter p k of a replica o i in a write operation w k(x). If w k(x) is an enriching write operation, the value x is written to the physical parameter s k of the replica o i in addition to the logical parameter p k , i.e. the state of the replica o i is materialized.

3.4 Read and write procedures of a data structure parameter

Next, we consider a read operation r 0 and a write operation w 0(x) for the data structure parameter p 0. First, a transaction T issues a write operation w 0(x) to write a value x in the data structure parameter p 0 in a write quorum Q 0w . In fact, w k(x) means an add or delete operation of a subobject x in a replica o i . A transaction T writes a value x to the data structure parameter p 0 of a replica as follows.

[Write procedure of w 0(x)]

  1. 1.

    Find a newest replica o i whose version counter vc 0 is maximum in a write quorum Q 0w . vc=o i .vc 0+1. o i .p 0=x and o i .vc 0=vc.

  2. 2.

    For every replica o j in the quorum Q 0w , o j .p 0=x and o j .vc 0=vc.

  3. 3.

    If w 0(x) is an enriching write operation, every replica o i is materialized by the materialization procedure mat(o i ) in the quorum Q 0w .

If a write operation w 0(x) is an impoverishing type of write operation like delete of a subobject, the value x is just recorded in the logical parameter p 0 but the physical parameter s 0 of the replica o i is not updated. On the other hand, each replica o i is materialized in an enriching type of write operation w 0. The version counter v 0 in every replica o i is increased to the maximum value vc.

Next, a transaction T issues a read operation r 0 to a read quorum Q 0r . Here, it is noted the transaction T has to read a whole state of a newest replica in the read quorum Q 0r while only a logical parameter p k is read in another read operation r k (k>0). The transaction T reads the data structure parameter p 0 of a replica in the read quorum Q 0r as follows.

[Read procedure of r 0]

  1. 1.

    Find a newest replica o i such that o i .vc k ≥o j .vc k for every parameter p k and for every replica o j in a read quorum Q 0r . If found, vc=o i .vc 0 which is the maximum value of the version counter vc 0 in the quorum Q 0r . The transaction T reads the whole state of the replica o i and go to step 4.

  2. 2.

    If not found, find a replica o i whose version counter vc 0 is maximum in the read quorum Q 0r . If the replica o i is found, vc=o i .vc 0. For each logical parameter p k (k≠0), find a replica o j whose version counter vc k is maximum, i.e. o j has the newest value of the logical parameter p k . o i .s k =o j .s k and o i .vc k =o j .vc k .

  3. 3.

    The replica o i is materialized by the materialization procedure mat(o i ). The transaction T reads the whole state of the replica o i .

  4. 4.

    For every replica o j (≠o i ) in Q 0r , o j .p k =o i .p k and o j .vc k =o i .vc k for every logical parameter p k .

In a read operation r 0, a newest materialized replica o i is first found in the read quorum Q 0r . If not found, a replica o i whose version counter vc 0 is maximum in the read quorum Q 0r is found. If some logical parameter p k of the replica o i is not newest, a replica o j with a newest value x of the logical parameter p k is found in the quorum Q 0r . The logical parameter o i .p k is changed with the newest value x. Then, the replica o i is materialized. The transaction T reads the materialized, newest replica o i in the quorum Q 0r . The logical parameter p k and version counter vc k in every replica o j are updated with the same values after step 4 as the newest replica o i in the quorum Q 0r after step 4.

Here, there are two ways to do for the other replicas than the newest replica o i after step 4.

  1. 1.

    Read-materialization (RM).

  2. 2.

    Just-read (R).

In one way, every replica o j in the quorum Q 0r is materialized by the materialization procedure mat(o j ). This means the physical state of every replica in the quorum Q 0r gets the newest after the transaction T reads the replica o i . This strategy is referred to as read-materialization (RM). MQB-RM stands for the MQB protocol with RM strategy.

In another way, only the replica o i is materialized. Here, only one replica o i is materialized in a read operation while the logical parameters p 0,p 1,…,p l of every other replica are newest values in a read quorum Q 0r . This strategy is referred to as just-read (R) one. In the MQB protocol, the R strategy is taken. Since only a newest replica o i which a transaction reads is materialized, the processing overhead of replicas can be reduced.

4 Evaluation

4.1 Environment

We evaluate the MQB and MQB-RM protocols compared with the QB protocol in terms of processing overhead of each replica. In the evaluation, we assume there is a set O (={o 1,…,o n }) of n (≥1) replicas o 1,…,o n . Each replica o i has logical parameters 〈p 0,p 1,…,p l 〉 where p 0 shows a data structure parameter and each p k is a QoS parameter (k=1,…,l). In the QB protocol, every replica is updated, i.e. materialized in a write quorum Q kw each time a write operation w k is performed on a logical parameter p k (k=0,1,…,l). That is, every write operation is a materialization type. In a read operation r k, the logical parameter p k in the newest replica o i is first read in a read quorum Q kr . Then, every other replica o j is updated to be the newest one in the read quorum Q kr . On the other hand, a replica is not materialized in an impoverishing write operation w k with the MQB protocol. In a read operation r 0, a newest replica o i is first found. Then, the replica o i has to has materialized if o i is not materialized.

Let γ (≤1) show the read ratio, i.e. the ratio of the number of read operations to the total number of operations issued by transactions. Here, (1−γ) indicates the write ratio. In this paper, we assume the sizes |Q kr | and |Q kw | of the quorums Q kr and Q kw are in inverse proportion to the read ratio γ and write ratio (1−γ). That is, if a read operation r k is more frequently issued than a write operation w k, the size of the read quorum Q kr is smaller than the write quorum Q kw . We assume |Q kr ∩Q kw |=2 in this evaluation. Each time an operation op k on the logical parameter p k is issued, the number of replicas are randomly selected to be included in a quorum Q k,op . In this evaluation, we assume the number l of QoS parameters is five, i.e. l=5.

In the simulation, we assume one transaction issues one operation op k. The totally 2,000 transactions are serially issued. A logical parameter p k to be manipulated in an operation op k is randomly selected (k∈{0,1,…,l}). A type of operation op∈{r,w} is also randomly selected so that the read ratio γ is satisfied. Then, replicas to be in a quorum Q k.op are randomly selected in the replica set O for each operation op k. In each write operation w k(x), a value x is written to the logical parameter p k of a replica o i . Here, the value x is randomly selected as x∈{0,…,99}. If w k(x) is an enriching type, the value x is also written to the physical parameter s k in the MQB protocol. If the value x is smaller than the physical parameter s k , i.e. current physical value of the kth parameter in the replica o i , the write operation w k(x) is considered to be an impoverishing type. Otherwise, w k(x) is an enriching type of write operation. Here, the value x is written to the logical parameter p k as well as the physical parameter s k . In a read operation r k, a transaction reads a newest replica o i in a read quorum Q kr . If a newest replica o i is not materialized, the replica o i is materialized and then is read by the transaction.

4.2 Evaluation results

Figures 3, 4, and 5 show the average numbers of materializations of replicas done for each operation in the MQB protocol, MQB-RM, and QB protocols. Figure 3 shows the average number of materializations of replicas for each operation in the MQB, MQB-RM, and QB protocols for the read ratio γ with n=10 and l=5. The number of materializations of replicas in the MQB and MQB-RM protocols can be reduced to about 30 % and 50 %, respectively, of the QB protocol for γ=0.5 as shown in Fig. 3. This means, the MQB and MQB-RM protocols imply the smaller processing overhead in each replica than the QB protocol. The processing overhead in the MQB protocol is the smallest.

Fig. 3
figure 3

Average number of materializations for one operation (n=10, l=5)

Full size image
Fig. 4
figure 4

Average number of materializations for read (n=10, l=5)

Full size image
Fig. 5
figure 5

Average number of materializations for write (n=10, l=5)

Full size image

Figures 4 and 5 show the average numbers of materializations for one read operation and one write operation, respectively, for read ratio γ in the MQB, MQB-RM, and QB protocols. Here, n=10 and l=4. In the MQB protocol, the average number of materializations for a read operation can be drastically reduced. For example, the average number of materializations in the MQB protocol is almost 10 % of the QB protocol for γ=0.8. On the other hand, the average number of materializations for a write operation in the MQB protocol is the same as the MQB-RM and can be reduced by 55 % compared with the QB protocol.

Figure 6 shows the number of materializations in the MQB, MQB-RM, and QB protocols for the total number n of replicas where l=5 and γ=0.5. As the number n of replicas increases, the number of materializations of replicas linearly increases in every protocol. For example, the numbers of materializations in the MQB and MQB-RM protocols are 20 % and 50 % of the QB protocol for n=100, respectively. The processing overheads of the MQB and MQB-RM protocols are smaller than the QB protocol. The MQB protocol supports the smallest processing overhead in the protocols.

Fig. 6
figure 6

Average number of materializations (l=5, γ=0.5)

Full size image

In the MQB protocol, there is a newest replica o i but the replica o i may not be materialized in a read quorum Q 0r when a read operation r 0 is issued. Let MR be the read materialization ratio, i.e. the ratio of read operations in which a newest, materialized replica is found to the total number of read operations issued (0≤MR≤1). Here, it is noted MR=1 for every read ratio γ in the QB protocol. That is, a transaction can necessarily find a newest, materialized replica in a read quorum with the QB protocol. In the MQB protocol, MR is smaller than the QB protocol since replicas are not necessarily materialized in a quorum. For example, MR=0.65 for γ=0.7 are MR=0.83 for γ=0.4 in the MQB protocol. That is, if 70 % (γ=0.7) of operations are read ones, there is probability 0.35 that a replica which is read is not materialized in the MQB protocol. MR=0.93 and MR=0.98 for γ=0.4 and γ=0.7, respectively, in the MQB-RM protocol. It takes time to materialize a replica. For example, for γ=0.5, if one hundred read operations are issued, we have to materialize a replica to perform 35 read operations in the MQB protocol while 5 read operations in the MQB-RM protocol. Hence, it takes a longer time to read a replica in the MQB protocol than the MQB-RM and QB protocols. One idea is that the MQB protocol is taken if the read ratio γ is smaller, e.g. γ≤0.4 and the MQB-RM protocol is taken for γ>0.4.

Next, we assume a read operation r 0 for the data structure parameter p 0 is randomly issued with probability δ while every write operation w k is randomly issued as discussed here. Another read operation r k (1≤k≤l) is randomly issued to read the logical parameter p k with probably (1−δ)/l. Here, δ=1/(l+1) means that every read operation r k (k=0,1,…,l) is randomly issued as evaluated in Figs. 4–7. The larger the ratio δ is, the more often the whole state of a replica o i is read. In order to read the whole state of a replica o i , the replica o i has to be materialized. Figure 8 shows the average number of materializations in the MQB, MQB-RM, and QB protocols for the data structure read operation ratio δ where n=10, l=5, and γ=0.6. The average number of materializations can be reduced in the MQB are MQB-RM protocols than the QB protocol. In the MQB protocol, the average number of materializations is almost independent of the data structure read ratio δ.

Fig. 7
figure 7

Materialization-ratio (n=10, l=5)

Full size image
Fig. 8
figure 8

Average number of materialization for r 0 (n=10, l=5, γ=0.6)

Full size image

5 Concluding remarks

In this paper, we discussed how to reduce the processing overhead of each replica of a multimedia object in the multimedia quorum-based (MQB) protocol. A multimedia object is characterized in terms of not only data structure parameter p 0 but also QoS parameters p 1,…,p l . There are read and write operations r k and w k for each parameter p k (k=0,1,…,l). There are enriching and impoverishing types of write operations. Some data has to be added to a replica in an enriching write operation like add. On the other hand, just data in a replica is removed in an impoverishing write operation like delete. In order to increase the performance of the MQB protocol, impoverishing write operations are just recorded in every replica while enriching operations are performed on every replica in a quorum. In a read operation to read a whole state of a replica, if a newest replica o i is not materialized in a read quorum, the replica o i is read after materialized. In the MQB-RM protocol, replicas in a read quorum are updated after a transaction reads the newest replica. We evaluated the MQB protocol and the MQB-RM protocol compared with the traditional QB protocol in terms of processing overhead of each replica. We showed the number of materializations of replicas can be reduced in the MQB and MQB-RM protocols compared with the QB protocol. The MQB protocol implies the minimum average number of materializations, i.e. smallest processing overhead.

In scalable systems, we have to more reduce the processing overhead of each replica. We are now discussing an extended MQB protocol where only some number, not all of replicas in a wrote quorum are materialized in a enriching type of write operation. We are also evaluating the communication overhead in addition to the processing overhead in a scalable system.