Mesaac Makpangou

Yvon Gourhant

Marc Shapiro

BOAR: A Library of Frag1nented Object Types for Distributed Abstractions

We present BOAR, a forest-structured library of predefined Fragmented Ob1ects ( FOs) encapsulating commonly used distributed abstractions. We identify three kinds of interaction FO types {channel, shar ing, and synchronization), which can be beneficially included in BOAR. A channel FO type encapsulates a remote or group invocation protocol A sha1i11.g FO type encapsulates a sharing mechanisms such as repli cation or partition.

Finally, a synchronization FO type encapsulates a synchronization mechanism. A FO programmer picks-up from BOAR, the FO types implementing the me ch an isms which fits best its needs.

Introduction

The object-oriented programming methodology is chiefly about re-use: one can design high level ob ject types that are then included in libraries for fu ture re-use [START_REF] I\eith | Object-oriented program support[END_REF][START_REF] Lea | Libg++, the GNU C++ library[END_REF]. Despite recent progress in extending the object programming methodology in a distributed environment, most existing object-oriented libraries lack support of distributed abstractions such as re mote invocation, multicasting, memory sharing, and distributed locking. Consequently, a programmer of a distributed application has to implement on his ow11, the distributed mechanisms that he needs. This makes designing a distributed application tedious and com plex. Furthermore, this solution is error prone and does not encourage the re-use of existing and/or ef!i cient code. To facilitate designing distributed applica tions, we propose the fragmented object model, along with its programming tools amongst which, I30A R, a library of object types encapsulating commonly used distributed abstractions.

Fragmented Objects (FOs) extend the object pro gramming methodology in a distributed environment [START_REF] Mesaac Makpa Ngou | Structuring dis tributed applications as fragmented objects[END_REF]. A FO provides two levels of abstraction. Exter nally, for its clients, a FO is a shared object. Inter nally, for its designer, it is a set of fragments, commu nicating through lower-level shared FOs called connec ti 1•e ob1ccts.

Typically, a connective object encapsulates a com munication protocol (e.g., RPC or parallel-RPC), a specific sharing abstraction (e.g. , replication, mi gration and partition), or a specific synchronization mechanism (e.g., locking, semaphore, rendez-vous and token passing).

I30AR provides to a FO designer, connective FO types encapsulating various implementations of com 2

Fragmented Object Model

As is common in object-oriented approach, a FO can be viewed at two diff erent levels of abstrac tion, corresponding respectively to a client's (abstract) view, and to the designer's (concrete) view.

Abstractly (for its clients), a FO is a single shared object. It is shared by several client objects, localized in diff erent address spaces, possibly on several sites. It is accessed via a strongly-typed interface. A FO can offer distinct interfaces to different clients.

Concretely (for the designer), a FO encapsulates a set of cooperating fragments. Each fragment is an elementary object (i.e., with a centralized representa tion).

We distinguish three fragment interfaces: the pri vate interface, the public interface, and the group in terface.

The private interface of a fragment is composed of internal methods, accessible only from within the frag ment.

The piiblic interface contains methods accessible by clients. The abstract interface of a FO is provided to some client via the public interface of a local fragment, that can be invoked locally. A client sees no difference between a fragment implementing the interface ex ported by the FO to this client, and the FO itself. The public interface of the fragment off ers transparency of the distribution to a client. A method of the public interface can be entirely implemented by the fragment itself, or it can trigger invocations to other fragments.

The group interface comprises those methods which are internal to the FO as a whole (i.e., which can be in voked remotely from other fragments). The group in terface concept extends type-checking to remote com munications.

The fragments cooperate using connective objects. A connective object is just another FO at a lower level of abstradion. The most primitive connective objects are the communication objects implemented by the system (for instance, communication protocols).

The types of parameters in the group interface of a FO may be totall y unrelated to the interface of its connective object. A compiler generates automati cally marshalling/unmarshalling code for methods of the group interface.

The mains benefits of the FO approach are:

• Separation of interface from implementation. Since, a FO is a distributed object, it is easy to switch between different policies for the same mechanism.

• Strongly type-checked remote communications.

• Reusa. bility of programmer-defined distributed shared objects.

• Support for diff erent levels of transparency,

• High-level communication abstractions.

• Support for concept of layered protocols. Mar shalling/unmarshalling conversions between these multiple layers are handled automatically and in a type-safe manner.

The FO model suits well for the object structuring of distributed abstractions. However, for application programmers to really benefit from this model, it is necessary to provide them with specific tools such as a library of predefined FO types implementing the com monly used distributed abstractions. BOAR is such a library.

3

Predefined Connective FO Types BOAR, (french acronym for Library of FO Types for Distributed Abstractions), is a forest-structured library of connective fO types. We distinguish mainly three class• es of connective FO types: channel, sharing and synchronization connective FO types. Examples of FO types of these classes are successively presented in Sections 3.1, 3.2 and 3.3.

Channels

A channel permits fragments of a same higher-level FO using it as a connective FO, to communicate ac cording to the client/server model. A fragment of the higher-level FO can plays the client role (i.e. it can in voke a method of the group interface implemented by another fragment), the server role (i.e. it implements a method of the group interface and can therefore be the target of a remote invocation from another fragment), or both roles.

Each fragment of the higher-level FO communi cating through a channel is bound with a fragment (or endpoint) of this channel. The channel endpoint bound with a client fragment offers it an interface to invoke its server counterparts; we will refer to this in terface as the channel interface. The endpoint bound with a server fragment is essentially in charge of re laying invocations.

There are two types of channel interface: a RPC-like interface for point-to-point channels, and a parallel-RPC-like interface for multipoint channels.

Channels impl ementing the same interface are orga nized hierarchically. The followin g two sections de scribe these two hierarchies of channels.

3.1.1

Point-to-point Channels

A point-to-point channel is characterized by its se mantics. Typically, a channel can enforce the maybe, at-least-once, at-most-once, or exactly-once semantics [START_REF] Spector | Performing remote operations effi ciently on a local computer network[END_REF].

A poin t-to-point channel is also characterized by the type of the synchrony that it enforces. We distin guish three kinds of synchrony: request/reply (upon a call, the client is blocked until the receipt of the reply); synchr on ous (upon a call, the client is blocked until the invocation message is delivered to the server);

and asynchronous where a client doesn't block at all. Finally, a point-to-point channel is characterized by the ordering in which invocations and replies are deliv ered to their destinations. We distinguish two ordering policies: datagram and FIFO.

No one of the cited semantics, synchrony or or dering policy can satisfy all distributed applications. Hence, in order to accommodate different applications, we provide an hierarchy of point-to-point channels im ple ment ing various combinations of these characteris tics. However, to allow application programmers to switch from one implementation to another, all point to-point channels have the same public interface.

The root point-to-point channel type is rpc(hannel.

A rpcCha nnel has two kinds of fragment types: channel and channelStub, associated respectively with a client and a server. A FO of type rpc(hannel implements both blocking and non-blocking remote procedure call.

It enforces the exactly-once semantics. It is datagram oriented (i.e. all calls and replies handed to this chan nel are eventually delivered to their destination, not necessary in their order sent).

Another is the a fifo(hannel channel. It differs from the basic one in that, invocations are delivered to the server in FIFO order.

Multi-point Channels

A multipoint channel implements a specific multicast protocol between fragments of a same FO. To simplify the addressing issue, all server fragments constitute a group. The group paradigm permits a client fragment to address all its server counterparts as a whole.

A multipoint channel is characterized by the qual ity of the service provided by its underlying multicast protocol (e. g., atomic, causal, fifo, or datagram order ing). It is also characterized by the management and the monitoring of its server group. Like for the point to-point channel, we have an hierarchy of multipoint channel, each implementing a specific multicast pro tocol, a specific group management and monitoring policy.

The root multi-point channel is multicast(hannel.

A FO of type muiticast(hannel has two kinds of frag ments: multi(hannel and a multi(hannelStub associ ated respectively with a client and a server fragment. The class multi(hannel (resp. multi(hannelStub) inher its from channel (resp. channelStub) .

A multicast(hannel supports both 1-to-N ( "paral lel") and 1-to-1-out-of-N ("functional") invocation. It also allows to address any subset of the server group. It relies on a reliable datagram multicast protocol (i.e., messages eventually reach their destinations, but no ordering is guaranteed).

Other available multi-point channels are fifoMul ticastChannel and atomicMulticastChannel channels.

They have the same client interface as the multicas t(hannel type. The fifoMulticastChannel guarantees FIFO delivery. The atomicMulticastChannel guaran tees that invocations are delivered to all destinations in the same order .

Sharing FO Types

A sharing FO type implements a specific sharing ab st racti on (e.g. , memory sharing, replication, migra tion, partition, stream). It provides to its clients (frag ments of a higher-level FO using it as a connective FO) a memory-like interface: some of them (called produc ers) write information that others (called consumers) will later explicitly read.

Sharing FO types are structured in several hierar chies. For each data structure (e.g., simple types 1 and records, un-typed raw memory access, lists, trees and graphs), there is an hierarchy of sharing FO types.

For each data structure, the root of its associated hierarchy of sharing FO types defines the generic in terface that all other sharing FO types will inherit. The operation code is produced by a compiler, dur ing the typed-checking phase of higher-level FOs, and is dynamically checked by the generated marshalling/ unmarshalling procedures.

Programmer-defined shared FOs can be easily im plemented by using a sharing FO as a connective FO.

For instance, a distributed directory can use a specific sharing FO type of type "list", implementing a specific sharing mechanism (e.g., list partitioning).

In For instance, for a large data structure, it is more ef ficient to replicate operations than to use the update protocol.

The designer of a replicated data structure will want a sharing FO type implementing the replication mechanism. Furthermore, he will want this sharing FO to guarantee the consistency of replicas of his data, and to enforce an efficient synchronization protocol.

A replic ation FO type offer a generic interface of ac cessing a replicated data structure. Each replication FO implements a specific consistency and/or replica tion protocol. As we already mentioned earlier, there is on� hierarchy of replication FO types per data struc ture.

A replication FO type uses two connective FO types: a channel for sending data between replica and a synchronization FO type for synchronizing access to replicas.

3.2.3

Partition

Partition FO types provide generic interface for fragmenting a data structure in several partitions.

Such a fragmentation allows to support parallel non confiicting accesses to the fragmented tree.

A partition FO allows to access transparently to all partitions of the data structure that its encapsulates.

Each FO type implements a specific fragmentation protocol. Consider for instance, a tree, fragmented into mu1tiple partitions, localized on several sites. A possible fragmentation can be similar to the one of V system (l], in which each part is a vertical slice, start ing at the root of the tree. Each partition is made of nodes and leaves associated with un-typed data. The set of partitions constitute the partition FO tree. The main role of such a partition FO type is to manage the distribution of the tree and to ensure its consistency.

3.2.4

Migration A Migration FO type implements a migration policy. This is a elementary object that moves on the site where it is accessed. Several Migration FO types en sure different synchronization policies.

3.3

Synchronization and Concurrency

Control

Distributed synchronization and concurrency con trol can be structured as FOs.

For instance, a Token FO allows its clients to ac quire/release a token. At one time, a single fragment holds the token. Each fragment of the Token knows the token owner. The acquire operation sends a re quest to the owner and blocks. The release operation (by the owner) broadcasts the list of requesters to all the fragments. Each f r agment determines the next owner using a deterministic algorithm. The Token FO has a connective FO of type channel.

Other

Synchronization types are semaphore, rendez-vous, barriers, monitors. Each of them will have a connective FO of type channel.

3.4

Examples of Application FO Types Exploiting BOAR FO Types

Applicat�on FO types are higher-level distributed shared objects, designed for specific classes of applica tion.

One can remark that an application FO type can also be re-used by several applications. For instance, a FO type implementing a replicated file abstraction can be used by many distributed file systems.

SOS Partitioned Naming Tree

The first example of application FO type is the Sos Tree, implementing a distributed tree structure, used by the SOS Name Service (4).

The SOS Name Service is implemented by server objects instantiated at boot time in separate "naming contexts", cooperating to process the clients' requests and to ensure the consistency of the distributed Name Space. This cooperation is through a connective ob ject of type SosTree.

SosTree manages a distributed Name Space and uses itself a Tree Partition FO as a connective object.

The former FO manages symbolic names and refer ences whilst the latter manages names and DataOb jects (section 3.2).

The fragmentation poli<:y of Sos Tree is similar to the one of V-system [l]. This policy is implemented by the Partition FO type. This choice is specified at binding time; in this case, at run-time for flexibility purpose. Actually, the fragmentation po�icy to solve conflicts, when adding a name to a partionned node, is simple. In the future, we investigate to define another policy based on load balancing. That will not affect the SosTree. Finally, BOAR permit a layering structuring of dis tributed abstractions (e.g., replication uses the chan nel and synchronization abstractions; hence these ab stractions are hidden to application programmer using a replication abstraction).

1

  Other sharing FO types of this hierarchy implement different policies of sharing this data structure. Fur thermore, different sharing FO types implementing a same sharing abstraction (e. g. , replication, partition) form an hierarchy too (i.e. a sub hierarchy of the global sharing hierarchy). For instance, the interface of the root sharing FO type for simple data types is read (DataObject)/write (DataObject), where DataObject is composed of an op eration code, un-interpreted data, and the size of data. Simple types are char, int, .... There is only one hierarchy for all these types.

3. 2 . 1

 21 Physical Memory SharingObjects on a same machine can communicate, through a physical shared memory.Access to a physical shared memory is implemented by a FO type, Shared Memory FO, which hides the internal representation of the memory (e.g. linear memory space, list of buf f ers, or array of structures). It ensures type-checked access and performs concurrency control.

3. 2 . 2 ReplicationA

 22 replicated object is characterized by the consistency which is enforced between its replicas. Well known ones are causal consistency, strong consistency, weak consistency and release consistency. All these consis tency semantics suit well for certain classes of applica tion. A replicated object is also characterized by the protocol used to update (or synchronize) •replicas (e.g., update, invalidate, replicate operations). Each proto col is appropriate for certain classes of data structure.

3. 2 . 5 StreamA

 25 Stream FO carries unidirectional information be tween producers and consumers. It provides two dif ferent interfaces: one for producer clients and one for consumer clients. The ordering (FIFO or LIFO) and the buffering policy diff ers between Stream types, which however all export the same interface. A Stream uses a Channel as a connective FO.

  the following sections, we pres.ent examples of

	sharing FO types. Section 3.2.1 presents the most
	primitive FO type. It defines access to physical shared
	memory. Sections 3.2.2, 3.2.3, 3.2.4 and 3.2.5 present
	generic sharing FO types for replication, partition, mi
	gration and stream. Finally, Section 3.4 presents a
	higher-level sharing FO type which hides the exact
	sharing mechanism to the programmer. It can then
	switch from one mechanism to another according to
	statistics, load-balancing or fault-tolerance considera
	tions.

  BOAR replicated FO types. In this case, a weak consistency is enough. The designer has just to implement lo•cal management of data; he relies on a replication FO type enforcing a weak replication con sistency. We presented the Fragmented Object Model and one of its tools, the BOAR library. Fragmented Objects extend the object program ming methodology in a distributed environment. One benefit of this model is that it enforces a clear separa tion between distribution mechanisms and tpolicies. BOAR provides FO programmers with predefined FO types implementing commonly used distributed mechanisms. These FO types are organized in several hierarchies, one per distributed abstraction. Connec tive FO types implementing a same abstra<:tion have the same public interface. This permits a FO program mer to interchange connective FO types implementing a same distributed abstraction. Ideally, a FO pro grammer can address critical distribution issues such as load-balancing, protection and fault-tolerance just by picking-up from BOAR the connective FO types implementing the mechanisms that he needs. BOAR is highly extensible: new connective FO types can be designed and added into BOAR for future re-use.

	3.4.2 A distributed mail application, which needs to repli Replicated Mailbox cate mailbox objects for availability purpose, can ben efit of the 4	Con cl us ion