Object-Based Group Protocol Based on Object-Based Ordered Delivery

全文

(1)Vol. 41. No. 2. Transactions of Information Processing Society of Japan. Feb. 2000. Regular Paper. Object-Based Group Protocol Based on Object-Based Ordered Delivery Katsuya Tanaka,† Tomoya Enokido,† Hiroaki Higaki† and Makoto Takizawa† Distributed applications are realized by cooperation of multiple objects. The state of an object depends on the order in which the objects exchange request and response messages. In this paper, we define an object-based precedent relation of messages based on a conflicting relation among requests. Here, only the messages to be ordered in the object-based system are ordered and the others are not ordered. We discuss a protocol that supports the object-based ordered delivery of request and response messages. An object vector for ordering messages is also proposed.. performs op and sends back a response message with the result of op. Here, the method op may further invoke other methods; that is, invocation is nested. The states of the objects depend on the order in which methods are performed. A conflicting relation among methods is defined for each object on the basis of the semantics of the object. If a pair of methods carried by request messages conflict in an object, the request messages have to be received in the computation order of the methods. Thus, the object-based ordered (OBO) relation among request and response messages is defined on the basis of the conflicting relation. In this paper, we present an Object-based Group (OG) protocol that supports the object-based ordered (OBO) delivery of messages, where only messages to be ordered at the application level are delivered to the application objects in the significant order. Takizawa, et al.13) show a protocol for a group of objects, which uses the real-time clocks in the objects. However, it is not easy to synchronize real-time clocks in distributed objects. We propose an object vector for ordering messages, which is independent of the group membership. In Section 2, we discuss the object-based precedency among messages. In Section 3, we discuss the OG protocol. In Section 4, we present the implementation and evaluation of the OG protocol.. 1. Introduction Distributed applications are realized by a group of multiple application objects. Many papers 3),11) have discussed how to support a group of objects with the causally ordered (CO) and totally ordered (TO) delivery of messages at the network level in the presence of message loss and stop faults of the objects. The group communication protocols imply O(n)O(n2 ) computation and communication overheads for a number n of objects in the group. Cheriton, et al.4) point out that it is meaningless at the application level to causally order all messages transmitted in the network. To reduce the computation and communication overheads, only messages required to be ordered by the applications should be causally delivered. Ravindran, et al.12) discuss how to support the ordered delivery of messages based on the message precedence explicitly specified by the application. Agrawal, et al.9) define significant requests that change the state of the object. Raynal, et al.1) discuss a group protocol for replicas of files where write-write semantics of messages are considered. The authors6) discuss a group protocol for replicas where a group is composed of transactions issuing read and write requests to the replicas. An object is an encapsulation of data and methods, that is, abstract operations for manipulating the data, which are higher-level than read and write operations. On receipt of a request message with a method op, an object o. 2. Object-Based Ordered Delivery 2.1 Object-Based Systems A group G is a collection of objects o1 , . . . , on (n ≥ 1) that cooperate by exchanging request and response messages in the network.. † Department of Computers and Systems Engineering, Tokyo Denki University 190.

(2) Vol. 41. No. 2. Object-Based Group Protocol Based on Object-Based Ordered Delivery. The objects are distributed in computers interconnected to the network. We assume that the network is less reliable and is asynchronous; in other words, that messages sent by each object are delivered to the destinations with message loss and not in the sending order, and that the delay time among objects is not bounded. An object oi can be manipulated only through methods supported by oi . Let op(s) denote a state obtained by applying a method op to a state s of the object oi . A pair of methods op 1 and op 2 of oi are referred to as compatible iff op 1 (op 2 (s)) = op 2 (op 1 (s)) for every state s of oi . op 1 and op 2 conflict iff they are not compatible. The conflicting relation Ci among the methods is specified when oi is defined on the basis of the semantics of oi . We assume that the conflicting relation Ci is symmetric but not transitive. A pair of request messages m1 with a method op1 and m2 with op2 conf lict iff op1 and op2 conflict. Suppose that a method op 1 is issued to an object oi . If op 1 is compatible with every method op2 being performed in oi , op 1 is started to be performed. Otherwise, op 1 has to wait until op 2 completes. Each time an object oi receives a request message of a method op, a thread is created for op. The thread is referred to as an instance of the method op in the object oi , which is denoted by opi . op commits only if all the actions performed in op complete successfully. Otherwise, op aborts. op may further invoke methods of other objects. Thus, the invocation is nested . 2.2 Significant Precedence First, we define the preceding relation among methods instances. A method instance opi1 precedes another method instance opi2 (op i1 ⇒i op i2 ) in an object oi iff op i2 is started after op i1 completes in an object oi . opi1 precedes opj2 (op i1 ⇒ op j2 ) iff op i1 ⇒i op j2 for j = i, op i1 invokes op j2 , or op i1 ⇒ op k3 ⇒ op j2 for some instance op k3 . opi1 and opj2 are concurrent (opi1 opj2 ) iff neither opi1 ⇒ opj2 nor opj2 ⇒ opi1 . opi1 opi2 means that opi1 and opi2 are interleaved in oi . A message m1 causally precedes another message m2 if the sending event of m1 precedes the sending event of m2 3),8) . In the totally ordered (TO) delivery, every pair of messages m1 and m2 not causally ordered are delivered to every common destination of the messages in the same order. That is, if some destination of m1 and m2 delivers m1 before m2 , every other destination delivers m1 before m2 . Suppose that. oi. oi opi1. oi m1. opi2 m1. opi2 m2. m2. z. z. m2. z. time ❄ (S1). time ❄ (S2.1). Fig. 1. opi1. opi1. m1. z. z z. time ❄ (S2.2). Send-send precedence.. oi m1. 191. oi opi1. z m2. z. time ❄ (R1) Fig. 2. m1. oi opi1. z. m1. opi1. z. opi2. opi2 m2 time ❄ (R2.1). z. m2. z. time ❄ (R2.2). Receive-send precedence.. an object oi sends a message m1 to objects oj and ok , and that the object oj sends m2 to ok after receiving m1 . Here, since m1 causally precedes m2 , the object ok has to receive m1 before m2 . For example, if m1 is a question and m2 is the answer of m1 , m1 has to be received before m2 . However, if m1 and m2 are independent questions, they can be received in any order. We define a signif icantly precedent relation “→” among messages m1 and m2 , where “m1 → m2 ” is meaningful for applications in the object-based system. Following cases exist for a pair of messages m1 and m2 that an object oi sends and receives: S. An object oi sends m2 after m1 (Fig. 1). S1. m1 and m2 are sent by opi1 . S2. m1 is sent by opi1 and m2 is sent by opi2 : S2.1. opi1 precedes opi2 (opi1 ⇒ opi2 ). S2.2. opi1 and opi2 are concurrent (opi1 || opi2 ). R. oi sends m2 after receiving m1 (Fig. 2). R1. m1 and m2 are received and sent by opi1 . R2. m1 is received by opi1 and m2 is sent by opi2 : R2.1. opi1 ⇒ opi2 . R2.2. opi1 || opi2 . We discuss how messages are significantly preceded for each of the cases. First, let us consider Case S (Fig. 1) in which an object oi sends a message m1 before m2 . In S1, m1 significantly.

(3) 192. Transactions of Information Processing Society of Japan. precedes m2 (m1 → m2 ) since m1 and m2 are sent by the same instance opi1 . In S2, m1 and m2 are sent by different instances opi1 and opi2 in oi . In S2.1, opi1 precedes opi2 (opi1 ⇒ opi2 ). Unless opi1 and opi2 conflict, there is no relation between opi1 and opi2 . Hence, neither m1 → m2 nor m2 → m1 . Here, m1 and m2 are referred to as significantly concurrent (m1 m2 ). Suppose opi1 and opi2 conflict. The output data carried by the messages m1 and m2 in a computation order “opi2 ⇒ opi1 ” may be different from “opi1 ⇒ opi2 ” because the state of the object oi obtained by performing the instances opi1 and opi2 depends on the computation order of opi1 and opi2 . Thus, if opi1 and opi2 conflict, the messages sent by opi1 have to be delivered before the messages sent by opi2 , i.e. m1 → m2 . In S2.2, opi1 opi2 . Since opi1 and opi2 are not related, m1 m2 . In Case R (Fig. 2), the object oi sends a message m2 after receiving m1 . In R1, m1 → m2 since the same instance opi1 receives m1 and sends m2 . Here, m1 is the request of opi1 or the response of a method invoked by opi1 . m2 is the response of opi1 or the request of a method invoked by opi1 . For example, suppose m1 is the response of op2 invoked by opi1 and m2 is the request of op3 . The output of op2 may be the input of m1 . In R2, m1 is received by opi1 and m2 is sent by opi2 (= opi1 ). In R2.1, opi1 ⇒ opi2 . If opi1 and opi2 conflict, m1 → m2 . Unless opi1 and opi2 conflict, m1 m2 . In R2.2, m1 m2 . [Definition] A message m1 significantly precedes another message m2 (m1 → m2 ) iff one of the following conditions holds: 1. An object oi sends m1 before m2 and a. m1 and m2 are sent by the same method instance, or b. a method instance sending m1 conflicts with a method instance sending m2 in oi . 2. The object oi receives m1 before sending m2 and a. m1 and m2 are received and sent by the same method instance, or b. a method instance receiving m1 conflicts with a method instance sending m2 . 3. m1 → m3 → m2 for some message m3 . ✷ [Theorem 1] A message m1 causally precedes a message m2 if m1 significantly precedes m2 (m1 → m2 ).. oi. oi m1 m2. Feb. 2000. opi1. z z. time ❄ (T1) Fig. 3. m1. m2. oi opi1. z z. opi2. time ❄ (T2.1). m1. opi1. opi2. z. m2. z time ❄ (T2.2). Receive-receive precedence.. [Proof ] In Case S, m1 causally precedes m2 since m1 is sent before m2 . Assume that m1 → m2 but that m1 does not causally precede m2 . In case R (Fig. 2), m1 → m2 and m1 causally precedes m2 . This contradicts the assumption. ✷ A message m1 does not necessarily significantly precede m2 even if m1 causally precedes m2 . 2.3 Object-Based Ordered Delivery We discuss how to deliver messages received. Suppose that an object oi receives a pair of messages m1 and m2 . The following cases exist for what instances in oi receive m1 and m2 : T. An object oi receives m2 after m1 (Fig. 3). T1. m1 and m2 are received by an instance opi1 . T2. An instance opi1 receives m1 and another instance opi2 receives m2 . T2.1. opi1 precedes opi2 (opi1 ⇒ opi2 ). T2.2. opi1 and opi2 are concurrent (opi1 opi2 ). In Case T1, the message m1 has to be delivered to the object oi before m2 if m1 significantly precedes m2 (m1 → m2 ). In T2, m1 and m2 are received by different instances opi1 and opi2 . In T2.1, first suppose that opi1 and opi2 conflict. If m1 or m2 is a request, m1 has to be delivered before m2 , since m1 → m2 . There is no case in which m1 and m2 are responses. Thus, messages destined for different instances cannot be delivered to the object oi in the order “→” unless at least one of the messages is a request. Next, suppose that opi1 and opi2 do not conflict. The messages m1 and m2 can be delivered in any order, even if m1 → m2 or m2 → m1 . If opi1 and opi2 are concurrent (opi1 opi2 ) in T2.2, m1 and m2 can be independently delivered to opi1 and opi2 . Next, suppose that an object oh sends a message m1 to two objects oi and oj , and that another object ok sends m2 to three objects oh ,.

(4) Vol. 41. No. 2. oh. Object-Based Group Protocol Based on Object-Based Ordered Delivery. oi. oph1. oj. ok. TO. m2 ❘. ✮. ✙. ❥ ✠. opk2. SO. op2 Fig. 5. time ❄. Fig. 4. OBO. CO. m1 op1. ❄. ❄. 193. ❄. Receive-receive precedence.. oi , and oj (Fig. 4). The objects oi and oj are common destinations of m1 and m2 . The following cases exist for the types of the messages m1 and m2 : C. Multiple objects receive messages m1 and m2 . C1. m1 and m2 are request messages. C2. One of m1 and m2 is a request message and the other is a response message. C3. m1 and m2 are response messages. In Case C1, suppose that the messages m1 and m2 are requests of methods op1 and op2 , respectively, and that op1 conflicts with op2 not only in the object oi but also in oj . If m1 m2 , oi and oj may deliver m1 and m2 in different orders. However, the state of oi obtained by performing the methods op1 and op2 may be inconsistent with oj because op1 and op2 conflict in oi and oj . In order to keep oi and oj mutually consistent, oi and oj have to deliver m1 and m2 in the same order. Thus, a pair of request messages m1 and m2 have to be delivered in every pair of common destination objects oi and oj of m1 and m2 in the same order if the request messages m1 and m2 conflict in oi and oj . In C2 and C3, m1 and m2 can be delivered in any order. Suppose an object oi receives a pair of messages m1 and m2 . First, suppose m1 m2 . If m1 and m2 are requests sent to one object oi , oi can deliver m1 and m2 in any order. Otherwise, the cases C1, C2, and C3 are adopted; that is, m1 and m2 are sent to multiple objects and are not necessarily request messages. We now define the object-based ordered (OBO) delivery of messages in the object-based system. [Object-based ordered (OBO) delivery] A message m1 is delivered before another message. Object-based ordered (OBO) delivery.. m2 in a common destination object oi of m1 and m2 if the following condition holds: • if m1 significantly precedes m2 (m1 → m2 ), • the same instance receives both m1 and m2 , or • m1 and m2 are received by different method instances opi1 and opi2 , opi1 conflicts with opi2 in oi , and one of m1 and m2 is a request, • if m1 m2 , • m1 and m2 are conflicting requests and m1 is delivered before m2 in every other common destination of m1 and ✷ m2 . Here, a message m1 is said to object-based precede (OB-precede) another message m2 (m1 m2 ) in an object oi if m1 is delivered before m2 in oi by the OBO rule. A message m1 is referred to as signif icant iff there is some message m2 such that m1 m2 or m2 m1 . Figure 5 shows a relation among the ordered deliveries of messages. Here, CO and TO stand for causally ordered delivery and totally ordered delivery, respectively. SO and OBO means significantly ordered delivery and object-based delivery, respectively. [Theorem 2] A message m1 causally precedes m2 if m1 significantly precedes m2 (m1 → m2 ). m1 object-based precedes m2 (m1 m2 ) if m1 → m2 . m1 totally precedes m2 if m1 m2 . ✷ In OBO delivery, only messages to be ordered in the object-based system are ordered. On the other hand, every message transmitted in the network is ordered in the CO and TO deliveries. Hence, fewer messages are ordered in OBO delivery than in CO and TO deliveries. 3. Object-Based Group Protocol 3.1 Object Vector The vector clock 10) V = V1 , . . . , Vn is widely used to causally order messages in group protocols3) . Each object oi manipulates a vec-.

(5) 194. Transactions of Information Processing Society of Japan. tor clock V = V1 , . . . , Vn . Each element Vj is initially 0 (j = 1, . . ., n). The object oi increments Vi by 1 each time oi sends a message m. The message m carries the vector clock m.V (= V ). On receipt of a message m , oi changes V as Vj := max(Vj , m .Vj ) for j = 1, . . ., n and j = i. A message m1 causally precedes another message m2 iff m1 .V < m2 .V . It is critical to discuss which method instances send messages for ordering only the messages significant in the applications. The object-based precedent relation “” among messages is defined for messages exchanged by the method instances, where the method invocations are nested, invoked in objects in a nested manner, while the causality is defined for messages exchanged by objects. Hence, a group is considered to be composed of method instances, not objects. If the vector clock composed of instances is used, the group has to be frequently resynchronized3),4),8)∼10),13) each time an instance is initiated and terminated. The vector clock can be used to causally order messages sent by objects but not by method instances. Hence, we newly propose an object vector to order only the significant messages in the object-based (OBO) precedence relation “”. The object vector is independent of what instances are being performed. The object vector V is a tuple V1 , . . . , Vn. where each element Vi shows the identifier of the method that an object oi has most recently performed. First, we discuss the identifier of a method instance opit . Each instance opit is given a unique identifier id(opit ). The object oi manipulates a variable oid, whose value is initially 0, showing the linear clock8) as follows: • oid := oid + 1 if an instance is initiated in oi . • On receipt of a message from opju , oid := max(oid, oid(opju )). When an instance opit is initiated in the object oi , the instance identifier id(opit ) is generated as a concatenation of the value of oid and the object number ono(oi ) of oi . Here, let oid(opit ) show oid of id(opit ). id(opit ) > id(opju ) if 1) oid(opit ) > oid(opju ) or 2) oid(opit ) = oid(opju ) and ono(oi ) > ono(oj ). It is clear that the following properties hold : I1. If opit is initiated after opiu in an object oi , id(opit ) > id(opiu ). I2. If oi receives a request opt from opju and then initiates opit , id(opit ) > id(opju ).. Oi. Feb. 2000 Oj. < 0, 0 > opi 1 < 0, 0 >. m 1i0 < 0, 0 >. < 0, 0 >. op j 2 < 0, 0 >. < 1i0, 0 > < 1i0, 0 >. time. Fig. 6. < 1i0, 0 >. Object vector.. Each action e in the instance opit is given an event number no(e). The event number is incremented by 1 each time opti sends a message. The event number is not changed for any action other than a sending action. The object oi manipulates a variable noi to give the event number to each action e, i.e., no(e) := noi in oi as follows: • Initially, noi := 0. • noi := noi + 1 if e is a sending action. Each action e in opit is given a global event number tno(e) as the concatenation of id(opit ) and no(e). An object oi manipulates a vector V i = V1i , . . . , Vni for i = 1, . . ., n. Each element Vji is initially 0. Each time an instance opit is initiated in the object oi , opit is given a veci. where Vtji := Vji for tor Vti = Vt1i , . . . , Vtn j = 1, . . . , n. Each element Vti is manipulated for opit as follows: • If opit sends a message m, noi := noi + 1 ; Vtii := id(opit ), noi ; m carries the vector Vti as m.V , where m.Vj := Vtji (j = 1, . . ., n). • If opit receives a message m from oj , Vtji := m.Vj ; • If opit commits, Vji := max(Vji , Vtji ) (j = 1, . . ., n); • If opit aborts, V i is not changed. Figure 6 shows two objects oi and oj . Initially, the object vectors V i and V j are 0, 0. and oid = 0 in oi and oj . An instance opi1 is initiated in oi where V1i = V i = 0, 0 . oid is incremented in oi , i.e. oid = 1. The identifier id(opi1 ) is “1i”. opi1 sends a message m to another instance opj2 . The message m carries the vector V1i (= 0, 0 ) to opj2 . Here, suppose m is a request message m of a method op2 . After.

(6) Vol. 41. No. 2. Object-Based Group Protocol Based on Object-Based Ordered Delivery. sending the message m, V1i is changed to 1i0, 0 where “1i0” is the global event number of the sending action of m. The message m carries the vector V1i (= 1i0, 0 ) to oj . On receipt of m, an instance opj2 is initiated where id(opj2 ) = 2j. Here, V2j is 1i0, 0 . If opj2 commits, the vector V j of the object oj is changed to 1i0, 0 . Otherwise, the vector V j is not changed. 3.2 Message Transmission and Receipt A message m includes the following fields: m.src = sender object of m. m.dst = set of destination objects. m.type = message type, i.e., request, responce, commit, or abort. m.op = method. m.d = data. m.tno = global event number m.id, m.no . m.V = object vector V1 , . . ., Vn . m.SQ = vector of sequence numbers sq1 , . . . , sqn . If m is a request message, m.tno is a global event number of the sending action of m. m.id shows the identifier of the method instance that sends m, and m.no indicates the event number in the instance. If m is a response message of a request m , m.tno = m .tno and m.op = m .op. An object oi manipulates variables sq1 , . . ., sqn to detect a message gap, that is, messages lost or unexpectedly delayed. Each time oi sends a message to another object oj , sqj is incremented by 1. Then, oi sends a message m to every destination object in m.dst. The object oj can detect a gap between messages received from oi by checking the sequence numbers. The object oj manipulates variables rsq1 , . . ., rsqn to receive messages. rsqi shows the sequence number of the message that oj expects to receive next from oi . On receipt of m from oi , there is no gap, that is, oj receives every message that oi sends to oj before m if m.sqj = rsqi . If m.sqj > rsqi , there is a gap message m where m.sqj > m .sqj ≥ rsqi . That is, the object oj has not yet received m that oi sends to oj . oj correctly receives m if oj receives every message m where m .sqj < m.sqj and m .src = m.src (= oi ). That is, oj receives every message that oi sends to oj before m. The selective retransmission to recover from the message loss is used in the protocol. If oj does not receive a gap message m in some time units after the gap is detected, oj requires oi to send m again. The object oj enqueues m in a receipt queue RQj. opi 1. Oi. 195. Oj. Ok. m1 op k 4 op j 3 op i 2. m2 op k 5. m3. op j 6 time. Fig. 7. Receipt vector.. even if a gap is detected on receipt of m. Suppose an instance opit in an object oi invokes a method op. Here, the request op may be sent to multiple objects. For example, a request is sent to multiple replicas. The object oi constructs a message m for the method op as follows and sends m to the destination objects: m.src := oi ; m.dst := set of destination objects; m.type := request; m.op := op; m.tno = m.id, m.no := id(opit ), noi ; sqh := sqh + 1 for every destination object oh in m.dst; m.Vj := Vtji for j = 1, . . ., n; m.sqj := sqj for j = 1, . . ., n; 3.3 Message Ordering Let us consider three objects oi , oj , and ok (Fig. 7). An instance opi1 in oi sends a message m1 to oj and ok . An instance opi2 is interleaved with opi1 in oi ; that is, opi1 and opi2 are concurrent (opi1 opi2 ). opi2 sends a message m3 to ok . An instance opj3 sends a message m2 to ok after receiving m1 . Here, m1 significantly precedes m2 (m1 → m2 ). ok has to receive m1 before m2 . However, m1 and m3 are significantly concurrent (m1 m3 ), since opi1 opi2 . Similarly m2 m3 . However, since opj3 is initiated after receiving m1 from opi1 and opi1 opi2 , m1 .V = m3 .V . Hence, m2 .V > m3 .V . Although ok can receive m2 and m3 in any order since m2 m3 , “m2 precedes m3 ” because m2 .V > m3 .V by the object vector. In order to resolve this problem, an additional receipt vector RV = RV1 , . . . , RVn is given to each message m received from oi . m.RV shows RV given to m. m.RV is the same as m.V except that m.RVi shows the global event number of.

(7) 196. Transactions of Information Processing Society of Japan Table 1 m m1 m2 m3. m.tno 1i0 2j0 2i0. Object vectors.. m.V 0, 0, 0 1i0, 0, 0 0, 0, 0. m.RV 1i0, 0, 0 1i0, 2j0, 0 2i0, 0, 0. the sending event of m for an object oi that sends m (i = 1, . . . n). m.RV is manipulated as follows: • m.RVi := m.tno; • m.RVh := m.Vh for h = 1, . . ., n (h = i); In Fig. 7, id(opi1 ) < id(opi2 ), because opi2 starts after opi1 starts. Hence, m1 .RV < m3 .RV , as shown in Table 1. The instance opi1 sends a message m1 to two objects oj and ok where m.tno = 1i0 and m.V = 0, 0, 0 . On receipt of m1 , the object oj enqueues m1 into a receipt queue RQj . Here, oj gives RV to m1 ; that is, m1 .RV = 1i0, 0, 0 while m1 .V is still 0, 0, 0 . Table 1 shows the values of tno, V , and RV of the messages. m1 .V < m2 .V and m1 .RV < m2 .RV . On the other hand, m2 .V > m3 .V but m2 .RV and m3 .RV are not comparable. A pair of messages m1 and m2 are ordered by the following rule: [Ordering rule] A message m1 precedes another message m2 (m1 ⇒ m2 ) if the following condition holds: if m1 .V < m2 .V and m1 .RV < m2 .RV , • m1 .op = m2 .op, or • m1 .op conflicts with m2 .op. else • m1 .type = m2 .type = request, m1 .op conflicts with m2 .op, and m1 .tno < m2 .tno. ✷ In Fig. 7, the instance opi1 sends a request m1 to the objects oj and ok where instances opj3 and opk4 are initiated. Then, opj3 sends a request m2 to ok . Here, m1 .V < m2 .V and m1 .RV < m2 .RV . Suppose opk4 conflicts with opk5 . m1 ⇒ m2 , since m1 .op and m2 .op conflict. Next, suppose that m2 is a data message and opk4 receives m2 after opk4 is initiated by m1 . Here, m1 ⇒ m2 , since m1 .op = m2 .op = opk4 . On the other hand, m1 .V = m3 .V , but m1 .RV < m3 .RV . Accordingly, we check whether m1 .op and m3 .op conflict. Since the instances opi1 and opi2 are compatible, m1 and m3 are not ordered in the precedent relation “⇒”. [Theorem 3] If a message m1 object-based precedes another message m2 (m1 m2 ), m1 ⇒ m2 .. Feb. 2000. [Proof] It is clear from the definition of the ordering rule. ✷ [Collorary] If a message m1 significantly precedes another message m2 (m1 → m2 ), m1 ⇒ m2 . [Proof ] From Theorem 2, m1 m2 if m1 → m2 . From Theorem 3, m1 ⇒ m2 if m1 m2 . ✷ The precedent relation “m1 ⇒ m2 ” is assumed to hold if the instances opi1 and opi2 are serially performed in Fig. 1 (S2.1). In S2.1, there are two cases in which opi1 and opi2 conflict and are compatible. If opi2 conflicts with opi1 , data carried by messages m1 and m2 depend on the computation order of opi1 and opi2 . Hence, “m1 ⇒ m2 ” has to hold. However, m1 and m2 are independent if opi2 is compatible with opi1 . Hence, there is no need for “m1 ⇒ m2 ” to holds. In the OG protocol, “m1 ⇒ m2 ” even if opi2 is compatible with opi1 . Further mechanisms are required not to order m1 and m2 . For example, each request message m sent by an object oi carries information on what request messages conflicting with m precede m. There is a trade-off between the complexity and overhead of additional mechanisms and the reduction of the delay time of messages obtained by reducing the number of significant messages. Thus, if “m1 ⇒ m2 ” only for a pair of conflicting requests m1 and m2 in S2.1, “m1 m2 iff m1 ⇒ m2 ” holds. 3.4 Message Delivery The messages in a receipt queue RQi are ordered in the precedent order ⇒. Messages not ordered in ⇒ are stored in RQi in the received order. [Stable message] Let m be a message that an object oi sends to another object oj and let m be stored in the receipt queue RQj . The message m is stable in oj iff one of the following conditions holds: 1. There exists such a message m1 in RQj that m1 .sqj = m.sqj + 1 and m1 is sent by oi . 2. oj receives at least one message m1 from ✷ every object, where m ⇒ m1 . The top message m in RQj can be delivered if m is stable, because every message preceding m in ⇒ is surely delivered. However, m cannot be delivered, because oj may perform requests conflicting with m.op. [Ready message] A message m in a receipt queue RQj is ready for an object oj if no.

(8) Vol. 41. No. 2 Oi. opi 1. Object-Based Group Protocol Based on Object-Based Ordered Delivery Oj. Table 2. Ok. m1 opk 2. opj 2. opk 3. m2. m m1 m2 m3 m4 m5. 197. Object vector and receipt vector.. m.tno 1i0 2j0 2k0 3k0 3j0. m.V 0, 0, 0 1i0, 0, 0 1i0, 0, 0 0, 0, 0 1i0, 0, 2k0. m.RV 1i0, 0, 0 1i0, 2j0, 0 1i0, 0, 2k0 0, 0, 3k0 1i0, 3j0, 2k0. m3 opi 3 opj 3 m4 m5 time. Fig. 8. Example.. method instance conflicting with the method ✷ m.op is being performed in oj . The messages in RQj are delivered by the following procedure in order to reduce the time needed for delivering messages. [Delivery procedure] While each top message m in RQj is stable and ready, m is delivered ✷ from RQj . [Theorem 5] The OG protocol delivers a message m1 before m2 if m1 object-based precedes m2 (m1 m2 ). [Proof] It is clear from Theorem 4. ✷ If an object oi sends no message to another object oj , messages in RQj cannot be stable. In order to resolve this problem, oi sends every object oj a message without data if oi had sent no data to oj for some predetermined δ time units. δ is proportional to the delay time between oi and oj . oj considers that oj loses a message from oi if oj receives no message from oi for δ or oj detects a message gap. oi also considers that oj loses a message m unless oi receives the confirmation of receipt of m from oj in 2δ after oi sends m to oj . Here, oi resends the message m. [Example] In Fig. 8, an instance opi1 is performed in an object oi and sends a request message m1 to objects oj and ok . On receipt of m1 , oj performs opj2 and ok performs opk2 . opk2 sends a request m3 to oi and oj . oi and oj perform opi3 and opj3 on receipt of m3 , respectively. opj2 and opj3 send responses m2 and m5 , respectively. opk2 and opk3 are concurrent in ok . opk3 sends a response m4 to oi . Suppose opj2 and opj3 conflict in oj . Each message m carries. tno, V, and RV as shown in Table 2. Since m3 causally precedes m4 , oi has to receive m3 before m4 . However, messages received in a receipt queue RQi are ordered by using the ordering rule. Since m3 .V (= 1i0, 0, 0 ) > m4 .V (= 0, 0, 0 ) but m3 .RV (= 1i0, 0, 2k0 ) and m4 .RV (= 0, 0, 3k0 ) are not comparable, m3 and m4 are not ordered in oi . Therefore, if oi receives m4 before m3 , oi delivers m4 without ✷ waiting for m3 . The linear clock8) is used to order method instances in the OG protocol. The size of the object vector is O(n), where n is the number of objects. According to the properties of the linear clock, an instance opi1 may not precede opj2 even if id(opi1 ) < id(opj2 ). If the vector clock is adopted, opi1 precedes opj2 iff id(opi1 ) < id(opj2 ). However, the volume of data that each message has to carry is O(n2 ), since the length of each element of the object vector is O(n). Therefore, to simplify the implementation, we adopt the linear clock mechanism for giving identifiers to the instances. 4. Implementation and Evaluation 4.1 Implementation An OG protocol module is implemented as a process of Solaris 2.6 in the Sun workstation. Each object oi has one OG protocol module OGMi (i = 1, . . . n). The OG module OGMi exchanges messages with other OG modules by using UDP 16) . OGMi delivers messages to oi in the object-based order “” by using the ordering rule. The OG module OGMi is realized by two threads, Rec for receiving messages and Snd for sending messages (Fig. 9). Rec and Snd share the variables showing the sequence numbers sq, rsq, the object vector V , the event number no, and the instance identifier id in the shared memory. The Snd thread takes messages from the object oi and sends the messages to the destination OG protocol modules. The Rec thread receives messages from other objects. The Rec thread orders the messages received by the ordering rule and delivers.

(9) 198. Transactions of Information Processing Society of Japan Oi. DQ Rec. shared memory. RQi. OGMi. i. OP 3 1. OP 1 OP 2 OP 3 OP 1 0 1 2 3. OP 3 4. OP 3 5. OP 2 4. OP 3 6. OP 2 7. OP 2 6. OP 3 7. Snd. V no tno sq rsq. OP 1 OP 1 OP 2 OP 3 2 2 3 1 (a). Fig. 10 Network. Fig. 9. OP 1 5. OP 2 3. OP 3 0 OP 2 0. Feb. 2000. Implementation of OG protocol.. the messages to the object oi . The Rec and Snd threads mutually exclusively manipulate the variables by using the semaphore. OGMi delivers messages in the delivery queue DQi of the object oi by the ordering rule. The OG module is written in C and the process size is 2 KB. Each object oi is realized by one process. The object oi takes the top message in the delivery queue DQi . On taking a request opt from DQi , an attempt is made to lock the object oi in a mode µ(opt ). If methods conflicting with opt are not being performed in oi and do not block in a block queue of oi , oi is locked in the mode µ(opt ). If oi can be locked, a thread for opt is created. Otherwise, opt blocks in a block queue of oi . Since the locking scheme is used, deadlock may occur. In this implementation, unless an object can be locked by a transaction in a fixed time after the lock request is issued, the transaction aborts in order to avoid deadlock. In this implementation, the semi-open locking scheme17) is adopted to release locked objects. Suppose that a method opt of the object oi invokes methods opt1 , . . ., optht on other objects oi1 , . . ., oiht (ht ≥ 1). Before performing a method optu , the object oiu is locked in a mode µ(optu ). If opt commits, the objects oi1 , . . ., oiht are released while oi is still being locked. If opt aborts, not only oi1 , . . ., oiht but also oi are released. Thus, the object oi is released if the method invoking opt completes or opt aborts. 4.2 Evaluation In the evaluation, three objects o1 , o2 , and o3 were implemented in a Sun Enterprise 450 with two CPUs (300 MHz) and 512 MB memory. Each of the objects o1 and o2 supports eight types of methods and o3 supports nine. OP 1 4. OP 2 5. OP 1 6. (b). OP 1 OP 3 7 8 (c). Invocation trees.. types of methods. Thus, a total of twenty-five types of methods are supported in the system. Some of the methods invoke other methods. Fig. 10 indicates tree structures showing invocations of methods. Here, opit shows that an method type opt is supported by an object oi . For example, a method op15 of the object o1 invokes three methods, op35 and op36 of o3 and op27 of o2 . The tree is referred to as invocation tree. In this paper, we assume that the methods in one invocation tree are compatible with each other while every pair of methods in different trees conflict with one another. For example, op11 is compatible with op10 , op11 , op21 , and op31 , since they are in the same tree, but op11 conflicts with op14 , op15 , and op16 . Each transaction is initiated τ [msec] after the first transaction is initiated. τ is a random number generated from the set of integers 0 to 9,999. Each transaction randomly selects one of the twenty-five methods supported by the objects o1 , o2 , and o3 . For example, one transaction selects op30 of o3 , which invokes a total of ten methods, and another transaction selects op27 , which invokes two methods, op37 and op38 . We measure the response time and the queue length of the receipt queue RQi in each object oi for the OG protocol and the messagebased group protocol. For the invocation trees shown in Fig. 10, the evaluation is iteratively performed until the average value of the response time and the queue length are saturated, because each transaction randomly selects one method. The average time for performing all the transactions is measured as shown in Fig. 11. Figure 11 shows that the OG protocol is about 50% faster than the messagebased protocol, because fewer messages are required to wait in the receipt queue in the OG protocol than in the message-based protocol. In addition, we measure the length of the receipt queue RQi of each object oi . Each time.

(10) Vol. 41. No. 2. Object-Based Group Protocol Based on Object-Based Ordered Delivery. Message−based protocol. 5.50. Average number of messages. 6.00. 5.00. Average time. OG protocol Message−based protocol. OG protocol. [x 10 3 sec]. 4.00. 3.00. 2.00. 1.00. 0.00. 199. 5.00. 4.50. 4.00. 3.50. 3.00. 0. 20. 40. 60. 80. 100. Number of transactions Fig. 11. Average time.. oi receives a message, the number qi of messages in RQi is obtained. The average number Qi is obtained by averaging qi from the starting time to the ending time of the evaluation. Figure 12 shows the average queue length of three objects for various numbers of transactions. The queue length in the OG protocol is 25–30% shorter than the message-based group protocol, because messages can be delivered without waiting for messages that are insignificant for the application. The computation overhead of the OG protocol module is almost the same as that of the message-based protocol module. 5. Concluding Remarks In this paper, we have discussed how to support the object-based ordered (OBO) delivery of messages. Whereas, in most group protocols, all messages transmitted in a network are causally or totally ordered, in this protocol, only messages to be causally ordered at the application level are ordered, to reduce the delay time. The system is modeled to be a collection of objects that support abstract methods. On the basis of the conflicting relation among methods, we defined the significantly precedent relation among request and response messages, and then defined the object-based precedence. We discussed the object vector for ordering messages in object-based systems. The size of the object vector depends on the number of objects, not the number of method instances. We. 50. 25. 75. 100. Number of transactions Fig. 12. Average queue length.. presented an implementation of the OG protocol and demonstrated through evaluation how the OG protocol reduces the response time of transactions. References 1) Ahamad, M., Raynal, M. and Thia-Kime, G.: An Adaptive Protocol for Implementing Causally Consistent Distributed Services, Proc. IEEE ICDCS-18, pp.86–93 (1998). 2) Bernstein, P.A., Hadzilacos, V. and Goodman, N.: Concurrency Control and Recovery in Database Systems, Addison-Wesley (1987). 3) Birman, K., Schiper, A. and Stephenson, P.: Lightweight Causal and Atomic Group Multicast, ACM Trans. Computer Systems, Vol.9, No.3, pp.272–314 (1991). 4) Cheriton, D.R. and Skeen, D.: Understanding the Limitations of Causally and Totally Ordered Communication, Proc.ACM SIGOPS’93, pp.44–57 (1993). 5) Enokido, T., Tachikawa, T. and Takizawa, M.: Transaction-Based Causally Ordered Protocol for Distributed Replicated Objects, Proc. IEEE ICPADS’97, pp.210–215 (1997). 6) Enokido, T., Higaki, H. and Takizawa, M.: Group Protocol for Distributed Replicated Objects, Proc. ICPP’98, pp.570–577 (1998). 7) Enokido, T., Higaki, H. and Takizawa, M.: Protocol for Group of Objects, Proc. DEXA’98, pp.470–479 (1998). 8) Lamport, L.: Time, Clocks, and the Ordering of Events in a Distributed System, CACM,.

(11) 200. Transactions of Information Processing Society of Japan. Vol.21, No.7, pp.558–565 (1978). 9) Leong, H.V. and Agrawal, D.: Using Message Semantics to Reduce Rollback in Optimistic Message Logging Recovery Schemes, Proc. IEEE ICDCS-14, pp.227–234 (1994). 10) Mattern, F.: Virtual Time and Global States of Distributed Systems, Cosnard, M. and Quinton, P. (Eds.), Parallel and Distributed Algorithms, pp.215–226, North-Holland (1989). 11) Nakamura, A. and Takizawa, M.: Causally Ordering Broadcast Protocol, Proc.IEEE ICDCS14, pp.48–55 (1994). 12) Ravindran, K. and Shah, K.: Causal Broadcasting and Consistency of Distributed Shared Data, Proc. IEEE ICDCS-14, pp.40–47 (1994). 13) Tachikawa, T., Higaki, H. and Takizawa, M.: Significantly Ordered Delivery of Messages in Group Communication, Computer Communications Journal, Vol.20, No.9, pp.724–731 (1997). 14) Tachikawa, T., Higaki, H. and Takizawa, M.: Group Communication Protocol for Realtime Applications, Proc. IEEE ICDCS-18, pp.40–47 (1998). 15) Tanaka, K., Higaki, H. and Takizawa, M.: Object-Based Checkpoints in Distributed Systems, Journal of Computer Systems Science and Engineering, Vol.13, No.3, pp.125–131 (1998). 16) User Datagram Protocol, RFC 0768 (1980). 17) Weikum, G. and Schek, H.J.: Concepts and Applications of Multilevel Transaction and Open Nested Transactions, Database Transaction Models for Advanced Applications, pp.516– 553 (1992).. (Received March 1, 1999) (Accepted October 7, 1999) Katsuya Tanaka was born in 1971. He received his B.E. and M.E. degree in Computers and Systems Engineering from Tokyo Denki University, Japan in 1995 and 1997, respectively. From 1997 to 1999, he worked for NTT Data Corporation. Currently, he is a assistant in the Department of Computers and Systems Engineering, Tokyo Denki University. His research interests include distributed systems, transaction management, recovery protocols, and computer network protocols.. Feb. 2000. Tomoya Enokido was born in 1974. He received his B.E. and M.E. degrees in Computers and Systems Engineering from Tokyo Denki University, Japan in 1997 and 1999, respectively. Currently, he works for NTT Data Corporation. His research interests include distributed systems, computer networks, and communication protocols. Hiroaki Higaki was born in Tokyo, Japan, on April 6, 1967. He received the B.E. degree from the Dept. of Mathematical Engineering and Information Physics, the Univ. of Tokyo in 1990. He is in the Dept. of Computers and Systems Engineering, Tokyo Denki Univ. He received the D.E. degree in 1997. His research interests include distributed algorithms and computer network protocols. He is a member of IEEE CS, ACM and IEICE. Makoto Takizawa was born in 1950. He received his B.E. and M.E. degrees in Applied Physics from Tohoku Univ., Japan, in 1973 and 1975, respectively. He received his D.E. in Computer Science from Tohoku Univ. in 1983. From 1975 to 1986, he worked for Japan Information Processing Developing Center (JIPDEC) supported by the MITI. He is currently a Professor of the Dept. of Computers and Systems Engineering, Tokyo Denki Univ. since 1986. From 1989 to 1990, he was a visiting professor of the GMD-IPSI, Germany. He is also a regular visiting professor of Keele Univ., England since 1990. He was a program co-char of IEEE ICDCS-18, 1998 and serves on the program committees of many international conferences. His research interests include communication protocols, group communication, distributed database systems, transaction management, and security. He is a member of IEEE, ACM, IPSJ, and IEICE..

(12)