Don Redmond

Donald Polkinghorne

LIFE IS GOOD: A NARRATIVE APPROACH TO GERONTOLOGICAL INTERVENTIONS

We live in a life immersed in narrative, recounting and reassessing the meanings of our past actions, anticipating the outcomes of future projects, situating ourselves at the intersection of several stories not yet completed. We are in the middle of our stories and cannot be sure how they will end; we are constantly having to revise the plot as new events are added to our lives."

Introduction:

The creative use of narrative theory and interventions has become increasing common with a range of ages. In the emerging sub-discipline of narrative gerontology, story-telling and story-listening techniques can be used to approach developmental concepts such as identity and spirituality [START_REF] Randall | Time, story, and wisdom: Emerging themes in Narrative Gerontology[END_REF]. This paper will focus on the case study of an extraordinary 92 year old subject and the range of gerontological concepts that surfaced throughout her interviewing process, the construction of a digital story narrated by the subject, and the reflections and lessons learned by the author.

The Story of Frances

I (the author) arrived for the first of two interviews with Frances on a January morning in Atlanta, GA. After being invited to the living room in her senior living facility and comfortable introductory talk, I began our digitally recorded interview. This initial session lasted for approximately an hour-and-a-half, then I returned for a second interview two weeks later. My questions were open ended, and although the interview didn"t fit a rigid script, my underlying goal was to listen for details from Frances" life so far that involved the display of strengths. Understandably, some focus was on her marriage of 58 years to her husband, of her two children, one of who succumbed to cancer not long after Frances" husband died in the early 2000"s. However, the interview also took a decidedly spiritual tone, and as I would learn, this spirituality would provide an important foundation of identity Frances continues to carry with her; "I was a senior in high school, and one night I heard the voice of God wanting me to be a missionary. I thought "this is crazy"; I had never known a missionary. I went to a church where we had services twice a month. I didn"t know anyone in full-time Christian work. And just being around anyone like that terrified me. But I kept having this call over and over again, and I could hear it so distinctly: "I just want you to be a missionary." I thought "I will never do that…And I"ll never forget it; I got up one night, and the moon was shining, and I went in to my parent bedroom. And I said, "God"s called me to be a missionary." And [my parents] said, "if God wants you to do that, we don"t want you to do anything else."

Frances followed the "calling," to seminary school, where she would meet her husband, and then to 20 years of service as a missionary in Nigeria; "Somehow I got the impression that when we got to Nigeria, the people there would be so happy to have us, the might bring a brass band!...And I learned right quickly; you know what, we"ve got to adjust to their way, they"re not going to adjust to ours…And the people were just wonderful, I didn"t have any problem relating…I have this strong feeling for women"s rights and I think it came from that experience."

Frances" story continued to her more recent past, and as she spoke, it became clear that she was still in Erikson"s Stage 7 of generativity, while also displaying a humility that most would link to wisdom. Further, Frances provided a wonderful example of what [START_REF] Freeman | Narrative foreclosure in later life: Possibilities and limits[END_REF] describes as narrative openness: the ability to continue to evolve independent of lifestage; "When [my husband] and I retired I continued my desire to help international folk find their way in the USA It seems new friends pop up constantly. I don"t know why God did that [at this age] but I"ve got such wonderful friends; Muslim, Hindu, even an Atheist are friends of mine. I mean, I don"t know what my role was in that, but they"re sweet and wonderful. I think that what it"s taught me is that everybody"s the same. And you have to make the first move, you can"t wait…my thing is that life is good. I"ve had some pretty rough spots to go through, but life is good." As CSN has evolved in our first year, we"ve been fortunate to conduct storytelling events with Atlanta-area community agencies serving adolescent and young adult populations having experienced especially difficult life events such as the premature death of a parent, abuse, and homelessness. Doctoral students are at various stages of conducting research by examining the stories of cancer survivors, siblings of victims of interpersonal violence, and women dealing with the diagnosis and emotional symptoms of uterine fibroids. Also, students in graduate level counseling courses have conducted service learning projects involving narrative interviewing, writing research papers, and presenting digital stories of populations that are some combination of "other-abled", recovering addicts, and over the age of 60.

Reflections

My interviews with Frances became CSN"s ceremonial first interview, and as many of us are learning, being an interviewer can, at the risk of understating, be as least as meaningful as being interviewed. As an example, my interviews with Frances resulted in several lessons and stoked curiosities;

First, it reinforced the fact that first impressions are not always accurate. When I sat down to interview Frances, I had little knowledge of her other than her age, and a referral who suggested she was spirited. Upon noticing Frances distinct "Southern" accent more prominently as she shared, "I was born in a small town in South Carolina…" an immediate concern flashed into my mind: could a white women growing up during this era possibly be unaffected by the deep-seated racism and classism of Jim Crow oppression?

Then, moments later, I saw why I along with many writers, counselors, and readers are drawn to narrative, particularly first-person narratives: they are often full of fascinating surprises. My education was further reinforced in creating Frances" digital story, with the significant help of doctoral student, Cherry Hymes. When Frances viewed a "first draft" of the digital story, she mentioned that the only thing missing was enough emphasis on her current life (obvious to me in hindsight, though not so at the time!). As McAdams discusses within a "life story" model of identity, Frances seemed to be immersed in a post-mythic stage where people "recast, revise, and retell their own life stories so that the past is seen as giving birth to the present and the future, so that beginning, middle, and ending make sense in terms of each other." (p.143).

Secondly, with advances in medicine, technology, and health-related research leading to both an increased life expectancy and richer experiences for adults in later life, perhaps the profession of counseling, and the field of narrative, should focus more on sharing the stories of someone like Frances? Could it help inspire others to form a future narrative based not on decline but on interpersonal adventure and new opportunities to experience generative activities?

Third, upon hearing of Frances" five grandchildren and five great-grandchildren, if future generations had access to digital stories about their ancestors, narrated with the actual voices of these relatives, might this help with the formulation of one"s own identity?

Epilogue

In early November of 2014, toward the end of an eventful year at CSN, including a CSN-sponsored Narrative Theory study abroad course-culminating in Paris at the 2014 Narrative Matters conference with a wonderful workshop led by Bill Randall for Mercer"s graduate counseling students-an unexpected "evite" popped up in my electronic mailbox. Frances was hosting her annual "International Thanksgiving Dinner." Thanksgiving is a U.S. holiday originating in the 1600"s and in addition to giving thanks and family gatherings, it"s known for eating. As I would learn, Frances" version of the holiday was a "potluck" and guests were asked to bring a dish from their home country. So in addition to food from the USA, delicacies, and friends, came from

  At the Center for the Study of Narrative (CSN) at Mercer University, founded in January of 2014, the author and his faculty, student, and community collaborators use principles of narrative theory to seek out and learn from stories of resilience. CSN is inspired by the work of Erik and Joan Erikson, the developmental and wellness model of the field of counseling, and the positive psychology movement led by Martin Seligman. Further, CSN is also indebted to the examples of Michael White and David Epson and the Dulwich Centre, Molly Andrews and her collaborators in East London at the Centre for Narrative Research, Dan McAdams at the Foley Center, and particularly William Randall at the Centre for Interdisciplinary Research in Narrative at St. Thomas University in New Brunswick, Canada.


E Anceaume

A K Datta

M Gradinariu

G Simon

A Virgillito

A Semantic Overlay for Self- * Peer-to-Peer Publish/Subscribe

Publish/Subscribe systems provide a useful platform for delivering data (events) from publishers to subscribers in an anonymous fashion in distributed networks. In this paper, we promote a novel design principle for self- * dynamic and reliable content-based publish/subscribe systems and perform a comparative analysis of its probabilistic and deterministic implementations. More specifically, we present a generic content-based publish/subscribe system, called DPS (Dynamic Publish/Subscribe). DPS combines classical content-based filtering with self- * (self-organizing, selfconfiguring, and self-healing) subscription-driven clustering of subscribers. DPS gracefully adapts to failures and changes in the system while achieving scalable events delivery. DPS includes a variety of fault-tolerant deterministic and probabilistic content-based publication/subscription schemes. These schemes are targeted toward scalability, and aim at reducing and distributing the number of messages exchanged. Reliability and scalability of our system are shown through analytical and experimental evaluation.

Introduction

The publish/subscribe paradigm has emerged in the recent years as an effective technique for building distributed applications in which information has to be disseminated from publishers (event producers) to subscribers (event consumers). Users express their interests in receiving certain types of events by submitting a filter on the event contents, called a subscription.

When a new event is generated and published, the publish/subscribe infrastructure is responsible for checking the event against all current subscriptions and delivering it to all users whose subscriptions match the event. Contentbased publish/subscribe systems allow complex filters on the event content, enabling the use of constraints such as ranges, prefixes, and suffixes. Combining expressiveness of subscription language and scalability of the infrastructure poses an interesting challenge that has inspired many researchers to explore this topic further. However, actual deployment of pub/sub architectures in real, large-scale systems is currently limited by their lack of self- * capabilities. In this work, self- * capabilities [START_REF] Anceaume | Towards a theory of self-organization[END_REF][START_REF] Babaoglu | A framework for the developments of agent-based peer-to-peer systems[END_REF] include 1) selforganization -the ability of the system to reduce the entropy of the system, for example, by making nodes form groups to improve or at least to maintain some global properties; 2) self-configuration -the ability of the nodes to set up their structural relationships; and 3) self-healing -the ability of the nodes to preserve their structural relationships despite the dynamicity of the system (joins, departures, or failures). Enhancing a pub/sub system with self- * capabilities allows an easier deployment and a more flexible adaptation in a larger spectrum of applications. Typical implementations of publish/subscribe systems (such as Siena [START_REF] Carzaniga | Design and Evaluation of a Wide-Area Notification Service[END_REF], Gryphon [START_REF] Bhola | Exactly-once Delivery in a Content-based Publish-Subscribe System[END_REF] and, recently, Kyra [START_REF] Cao | Efficient Event Routing in Contentbased Publish-Subscribe Service Networks[END_REF]) rely on a network of dedicated servers (usually called brokers) that are controlled by administrators in charge of repairing and maintenance interventions. However, in dynamic decentralized scenarios such as peer-to-peer networks this architecture is not feasible, because the high dynamicity of the context requires the topology of the network to be frequently rearranged to face changes due to node joining, leaving and failing. Scribe [START_REF] Castro | Scribe: A large-scale and decentralized application-level multicast infrastructure[END_REF] and Bayeux [START_REF] Zhuang | Bayeux: An architecture for scalable and faulttolerant wide-area data dissemination[END_REF] are two topic-based systems having self- * capabilities. They both make use of a DHT (Distributed Hash Table ). A single node is responsible for matching and delivering all notifications related to a specific topic, which is the root of a dynamically-built diffusion tree for events. Combining content-based expressiveness with self-organizing capabilities of DHT-based overlays is discussed in several papers [START_REF] Triantafillou | Content-based Publish/Subscribe over Structured P2P Networks[END_REF][START_REF] Gupta | Meghdoot: Content-based publish:subscribe over p2p networks[END_REF][START_REF] Baldoni | Content-based publish-subscribe over structured overlay networks[END_REF]. Meghdoot [START_REF] Gupta | Meghdoot: Content-based publish:subscribe over p2p networks[END_REF] and [START_REF] Baldoni | Content-based publish-subscribe over structured overlay networks[END_REF] work on top of a CAN and a Chord overlay, respectively to store the system subscriptions. The main difficulties in designing content-based pub/sub on top of DHTs are: (i) mapping content-based subscriptions into a single key space and (ii) ensuring the persistence of subscriptions despite the dynamicity of the underlying overlay. Methods to map content-based subscriptions to DHT addresses are described in [START_REF] Triantafillou | Content-based Publish/Subscribe over Structured P2P Networks[END_REF][START_REF] Baldoni | Content-based publish-subscribe over structured overlay networks[END_REF]. The mapping requires subscriptions to be moved from the issuing node to a set of selected "rendezvous" nodes. Mapping may impose some restriction on the constraints applicable in subscriptions with respect to the general language supported by broker-based systems. Typically, string constraints like prefixes and suffixes cannot be easily mapped to a set of keys. Moreover, subscriptions are usually replicated on several rendezvous nodes, and large subscriptions (i.e., subscriptions that possibly match a large number of events) may have many copies. Replication is also used in order to maintain the persistence of subscriptions [START_REF] Gupta | Meghdoot: Content-based publish:subscribe over p2p networks[END_REF]. This is required because a subscriber can lose its subscriptions if a rendezvous node fails.

Contributions of the Paper

In this paper, we promote a novel design principle for reliable content-based publish/subscribe architectures with self- * capabilities. Our system, namely DPS, is not based on a network of brokers. Subscribers coordinate among themselves on a peer-to-peer basis to construct optimized event diffusion paths without any human intervention. More precisely, we propose a subscription-driven semantic overlay in which subscribers self-organize according to similarity relationships among their subscriptions. In DPS, two subscribers are considered similar when they share a common attribute of a subscription. Similar subscribers are logically connected into the same group. Groups of subscribers self-configure to form tree structures such that only one tree is built per attribute. No mapping of DHT-based overlay is needed. Virtually all types of attributes and constraints can be directly supported. Moreover, subscriptions are not replicated: a subscription is maintained only at the corresponding subscriber. Differently from a previous solution for semantic-driven pub/sub overlay [START_REF] Felber | Semantic peer-to-peer overlays for publish/subscribe networks[END_REF], DPS does not assume the complete knowledge of the network to compute the neighbors of a node. Thus, each subscriber has to keep track of a limited number of its neighbors regardless of the size of the system, and the effect of node failures is confined within a bounded number of neighboring groups.

The general design principles of the DPS overlay can be instantiated with different algorithms to i) traverse the tree for propagating a subscription or a publication across the groups and ii) realize the communication inside a group and between groups. Tree traversal and communication approaches can be combined to design DPS implementations that cater the needs of different deployment contexts. In particular, we propose two different techniques for tree traversals (namely, root-based and generic) and two different approaches for communication (leader-based and epidemic). The epidemic approach is based on gossiping of events that obtains high probabilistic guarantees of delivery even in presence of frequent failures. With respect to the gossipbased algorithms for publish/subscribe described in [START_REF] Baehni | Data-Aware Multicast[END_REF], our system supports expressive content-based addressing. Gossiping techniques for content-based publish/subscribe have been exploited in [START_REF] Costa | Epidemic algorithms for reliable content-based publish/subscribe: An evaluation[END_REF], but without a self-organizing overlay.

DPS is evaluated through an extensive simulation and analytical study in which it has been tested using different types of workload that model realistic application scenarios, and comparing the different implementation styles. Results show that the DPS overlay allows to massively reduce the number of visited nodes with respect to a broadcast (from 75% to 90% of the nodes less). Moreover, simulations show the self-healing capabilities of DPS, even when subject to severe failure conditions, and the overall scalability of the approach, that can provide high degrees of reliability without cluttering the network with control messages.

The rest of the paper is organized as follows. In Section 2, we present the system model and the problem statement. In Section 3, we define the logical backbone of DPS, introducing the concept of similarity on which the logical structure of the DPS overlay is based. Several algorithms for subscriptions and publications, and for communicating within the groups are presented in Section 4. Analytical and experimental evaluations of DPS are studied in Section 5. We make some closing statements on the proposed and future work in Section 6. Finally, due to lack of space, the pseudo-code of the algorithms, proof of correctness of DPS and proof of its self- * properties are presented in a longer version of this paper [START_REF] Anceaume | DPS: Self* dynamic reliable content-based pub-5 Due to space limitations[END_REF].

Framework

We assume a finite, yet unbounded dynamic set of nodes. The set is dynamic in the sense that nodes can join or leave at an arbitrary time. Each node is associated with a unique identifier. In a publish/subscribe system, Nodes cooperate to send (publish), relay, and receive (notify) special messages, namely events (or publications). The interest of a node in a set of events is referred to as subscription, and is expressed as a filter defined on the content of the events. In order to inform the system about their subscriptions, nodes invoke a Subscribe primitive. The invoking node is called a subscriber. Additionally, nodes can publish events by invoking a Publish primitive. We say that a node is notified of an event when the system invokes a Notify primitive on it.

We consider a content-based publish/subscribe data model [START_REF] Gupta | Meghdoot: Content-based publish:subscribe over p2p networks[END_REF] where both subscriptions and events use as building blocks a finite, yet unbounded universe of typed attributes. A content-based subscription (filter) is a conjunction of predicates, i.e., F = AF 1 ∧ . . . ∧ AF j , where AF i is ). An event is a conjunction of equalities over the attributes' universe. More precisely, an event is denoted as

E = AV 1 ∧ . . . ∧ AV k ,
where

AV i = (name i = v i )
, where v i is the value of the attribute. An event predicate AV matches a subscription predicate AF (denoted as AV ∈ AF ) if the attribute names are the same in AV and AF and the attribute value in AV is in the range defined by AF . An event matches a subscription iff for all the predicates in the subscription, a corresponding matching value appears in the event.

Finally, it is important to note that the number of attributes for events and subscriptions is not fixed. That is, each single subscription or event can include an arbitrary number of predicates and no prior coordination among nodes is necessary to agree on the event space.

The DPS Overlay

In this section, we describe the construction and main features of the overlay scheme dedicated to the DPS pub/sub system. The DPS overlay is subscription driven: subscribers locally self-organize according to their interests and the resulting logical structure is a virtual forest of logical trees, where each tree is associated with an attribute and only one tree is maintained per attribute. Each vertex of a tree is labeled with a predicate (filter on the tree attribute). In the following, we present the relationships that enable subscribers to self-organize according to their subscription similarity. The two relationships lead to the construction of an overlay which is suitable for efficient event dissemination according to the following two principles: i) The more likely a subscriber is to receive a matching event, the higher it is placed in the tree; ii) All subscribers that are likely to receive a common subscription are made neighbors of each other. Efficient paths for events are thus created maintaining only a node's overlay neighbors: if a subscriber does not match an event, all its successors in the tree will neither and the event can be safely filtered out.

Two nodes are similar when they share at least one common predicate in at least one of their subscriptions.

Definition 1 (Similarity Relation ) Let p and s be two nodes representing two subscription filters F p and F s , respectively. Assume that F p = ∧ i∈I AF Fp i and F s = ∧ j∈J AF Fs j , where I and J are the sets of indices for predicates in F p and F s , respectively, and AF Fq m is the predicate AF m in the subscription filter F q . p and s are similar with respect to a predicate AF , denoted as p AF s iff ∃k ∈ I, k ∈ J ::

AF F1 k = AF F2 k (= AF ).
A semantic group (or simply group) is identified through a group predicate which is the common predicate on which the members of the groups are similar. For example, the group labeled A > 3 refers to the group of all the subscribers that include A > 3 in their subscription predicate:

Definition 2 (Semantic Group) Let G AF be a set of nodes and AF a predicate. G AF is an AF group iff ∀p, s ∈ G AF :: p AF s.
The group predecessor relation imposes a hierarchical ordering among the groups that is based on the predicate inclusion relation. A predicate AF 2 is included in a predicate AF 1 if all the events matching AF 2 also match AF 1 .

Definition 3 (Predicate Inclusion)

Let AF 1 and AF 2 be two predicates and AV an event.

AF 2 ⊂ AF 1 iff ∀AV ∈ AF 2 , AV ∈ AF 1 .
Two groups are related through the group predecessor relation when their respective group predicates are related by the above defined predicate inclusion relation.

Definition 4 (Group Predecessor Relation

pred → ) Let G 1 and G 2 be two labeled groups with respect to the predicates (or labels) AF 1 and AF 2 , respectively.

Then G 1 pred → G 2 iffAF 2 ⊂ AF 1 and ∃G 3 such that G 1 pred → G 3 pred → G 2 .
Each attribute is "owned" by a unique subscriber. For instance, in Figure 1.b, the owners of the trees labeled "a", "b", and "c" are subscribers s 0 , s 6 , and s 7 , respectively. Trees are connected among each other, for example by letting all owners know each other or by keeping at each node a cache of nodes belonging to other trees 1 .

A subscriber joins the tree corresponding to only one of the attributes of its subscription. This attribute can be arbitrarily chosen without affecting the correctness of the solution since each event is published in each logical tree that matches every attribute of the event. We decided to decompose a subscription into its attributes, rather than maintaining a single tree (as done in [START_REF] Felber | Semantic peer-to-peer overlays for publish/subscribe networks[END_REF]), because of the generality of the content-based language that does not always allow to determine a predecessor between two subscriptions (for example, consider subscriptions S 1 : (0 < a < 10) ∧ (b > 0) and S 2 : (1 < a < 12) ∧ (2 < b < 4)). The drawback of this choice is that subscribers also receive events that match only a part of their subscription (false positives). Moreover, the number of false positives is likely to grow when more attributes are present. Thus we deem our approach more effective especially when few attributes are considered.

Finally, following only the above definitions, some types of predicates like equality or substrings may be placed at different places in the tree. For example, the group for predicate a = 4 in the tree for attribute "a" may be placed below the group for predicates a > 2, a > 3, a < 11, or a < 20. These ambiguities may create problems while trying to locate a group upon subscription. To remove them, we impose two additional constraints on the tree construction as follows: Constraint C1: All groups related to an ambiguous predicate must be placed in the tree following a unique consistent convention. For example, for numerical attributes, equality predicates are placed as successors of either the greater-than or the less-than groups. Constraint C2: A group G related to an ambiguous predicate is placed as successor of its immediate predecessor G m , s.t. there exist no groups that are predecessors of both G m and G.

As previously said, our logical overlay is constructed by the self-organization of subscribers according to their subscription similarity. Other approaches [START_REF] Riabov | New algorithms for content-based publication-subscription systems[END_REF][START_REF] Cao | Efficient Event Routing in Contentbased Publish-Subscribe Service Networks[END_REF] group similar subscribers by applying a partitioning criteria over the event space. All nodes having subscriptions that fall into a common partition are grouped. We chose the similarity over the partitioning method because it does not require prior agreement among the nodes, does not depend on the number of nodes, and reduces the number of non-matching messages received by nodes in a group.

DPS Algorithms

In this Section, we present algorithms for the construction of the DPS overlay and the publication and subscription diffusion. These algorithms are organized into two classes: tree traversal algorithms, that concern how to locate the position of a group when creating, joining or publishing into a group, and communication algorithms, that regard how to exchange publications and subscriptions between groups and among nodes of a same group. The following data structures are used in the DPS algorithms: groupview: list of pointers to nodes inside the group.

predview, succview: two ordered lists of K pointers to nodes in successor/predecessor groups. That is, they point not only to nodes in the direct successor group but also to successors/predecessors at upper/lower levels, in order to handle multiple concurrent failures involving a whole group at once. The lists are ordered according to the nodes predicates. If there are F nodes in the list and a new node is inserted, a node is removed from the bottom of the list. In groups with multiple branches, a node must have one succview list for each of its successor groups.

Tree Traversal

Prior to subscribing or publishing an event, a node should traverse the tree in order to locate the position of the group it has to belong to, in case of subscription, and all the groups hosting subscribers for the event, in case of publication.

Traversal starts by a contact point in the trees related to the subscription or the publication. While subscribers only need to contact one tree, a publisher has to traverse all the trees corresponding to each attribute within the event. Being the trees connected among each other, it is always possible to locate a contact point in any of the trees, for example by propagating a request message with random walks. If there is no tree for an attribute (i.e., no contact point is found at the end of the random walks), a new tree is created and the first subscriber becomes its owner. It is possible that multiple trees for a same attribute are created, when two nodes subscribe concurrently. In order to further reduce the probability of this already rare event, the node that creates a tree starts periodically a new traversal, in order to detect duplicate trees and merge them into one.

In the root-based approach, visit of the tree starts from the root and proceeds only downwards, while in the generic approach any node can be chosen as a starting point and the visit goes in both directions. Root-based allows to obtain lower latency but imposes high stress on the root node and requires this node to always be known. In the generic approach a visit requires in general more messages but the load is more evenly balanced and the contact point can be any node in a tree. Subscription Scheme. The subscription process exploits three primitives, namely FIND GROUP, SUBSCRIBE TO and CREATE GROUP, respectively used for locating the group of similar subscribers, joining to it or, if it does not exist, creating a new one in the proper position in the tree. A subscriber s issuing a new subscription has to traverse a tree in order to find its position. Each step in the traversal consists in a call to FIND GROUP on the next node.

Figure 2. Tree Traversal Example

Figure 2 shows an example of a new group creation. The black line shows the path followed by the subscription a = 3 issued by subscriber s using the root-based approach. The subscription is received by group a > 2. Since this group is the smallest possible predecessor of group a = 3, it is considered the designated predecessor for the subscription (Constraint C2). As this group does not exist, it is created below a > 2 and s is added to it. The paths followed by the generic approach are represented by gray lines -solid and broken lines for the contact points s 9 and s 5 , respectively.

When an appropriate group for s is located, a SUBSCRIBE TO message is sent back to s to join the group. If no group matches s's predicate, then a CREATE GROUP message is sent back s. Each time a new group is created, event propagation is blocked in the predecessor, by setting a proper variable. The variable is reset when data structures related to the new successor are updated. Allowing publications and subscriptions during group construction may result in events not delivered to the new successor group, or more seriously, creating incorrect groups in the trees in case of concurrent group creations. Publication Scheme. The visit of the trees in a publication is invoked through the PUBLISH primitive from the contact points in all the trees corresponding to the attributes in the published event. An event received by a group is matched against the group predicate. If the event matches the group predicate, it is propagated inside the group (through the PUBLISH GROUP primitive).

In the root-based approach downstream propagation along the tree continues as long as the event matches the group predicate; it stops otherwise. The successor relation between groups ensures that no matching subscribers are present in any successor groups. So, the entire branch of the tree can be safely excluded from the event propagation. Consider the right side of Figure 2. In the root-based approach (the black line), the publication a = 4 is forwarded downstream from the contact point to all the groups with predicates matching the publication. Differently, in the generic approach, if the event does not match the group predicate, it still has to be forwarded upstream to the pre-decessor. Otherwise, if the event has been received by j from its predecessor, it is forwarded to j's successor only if it does match j group predicate. In Figure 2 when the publication starts from the group a < 4, it is propagated up through both branches (dashed gray lines) through all the matching groups. Group a > 2 also needs to forward the publication to its successor in order to reach group a = 4.

Communication within the DPS System

Leader-Based Communication

Each group in each logical tree contains a special node which behaves as the leader of the group. Communication between different groups is realized via their respective leaders. K c additional leaders are maintained to deal with the leader failure. A node becomes the leader of a group as soon as it creates its own group or remains the only member of a group. Co-leaders are selected as the first K c nodes that joined the group directly after the leader. Only leaders and co-leaders maintain the predview and succview lists. They also maintain the whole group in their groupview. A regular member (i.e., neither a leader nor a co-leader) only has leaders and co-leaders in their groupview.

Leader-based Subscription. The subscription process is realized by implementing the CREATE GROUP and SUBSCRIBE TO primitives. Both are invoked on the new subscriber by the leader of the predecessor group. Upon receipt of such primitives, the new subscriber updates its variable group. If it becomes the leader or co-leader of a new group, it updates succview.

Leader-based Publishing. The publication process is realized by implementing the PUBLISH GROUP primitive. An event received by a group through this primitive is always redirected to the group leader. The leader propagates all the events it receives to all the group subscribers. Each subscriber upon receipt of an event notifies its application only if the event matches one of its subscriptions.

Epidemic Communication

In epidemic communication [START_REF] Birman | Bimodal multicast[END_REF][START_REF] Kermarrec | Probabilistic Reliable Dissemination in Large-Scale Systems[END_REF][START_REF] Baehni | Data-Aware Multicast[END_REF], each member of a group communicates with a subset of members of other groups. In particular, each nodes stores its predview, succview and groupview, that contain only a subset of the group's nodes. In contrast with the leader-based approach, several copies of a message may traverse the group. This guarantees a higher fault-tolerance at the price of message duplication. Data structures are updated for every change in the membership and maintained by periodic gossiping. Epidemic Subscriptions. Similar to the leader-based approach, epidemic propagation of subscriptions is realized through the CREATE GROUP and SUBSCRIBE TO primitives. An additional primitive, GOSSIP SUB, is required to update the views and propagate the update within the group. Upon receipt of such primitives, the new subscriber updates its variables groupview and succview. View update messages are gossiped by each node to F s other nodes in the group. F s is called the subscription fanout. When a gossip message is received by a node, it is forwarded with probability p, a parameter of the algorithm. To stop the propagation, probability p is reduced proportionally to the number of times the message is forwarded. Note that a node issuing a new subscription can receive more than one CREATE GROUP or SUBSCRIBE TO messages if the diffusion started from more than one contact points. This does not require any specific check in the algorithms. Epidemic approach is prone to undesired behavior when two similar subscriptions are issued concurrently. In particular, if two different nodes in a particular group receive the subscription requests concurrently, two groups corresponding to the same predicate are created. According to our simulation study, this behavior is very infrequent and does not harm the correctness of the system. The system continues behaving according to its specification, only suffering from a non-optimal use of resources.

In order to limit these situations, a merge process is considered: nodes periodically send a view update message to their successors in the succview, containing the whole succview. Node receiving the update have the opportunity of adding to their groupview some nodes in the group that they do not know, leading to a merge of disjoint groups. Epidemic Publishing. Publications are diffused within a group with a simple gossiping. That is, each node forwards the message to k of its neighbors. As for subscriptions, the probability of forwarding an event in the group decreases proportionally to the number of times the event is forwarded.

Self-healing of DPS Overlay

The DPS overlay is able to self-heal when nodes in the overlay leave by voluntary departures (unsubscriptions) or failures (crashes), that can provoke partitioning between two groups in the tree or inside a same group. Nodes in the predview and succview structure are periodically monitored for failures. If one node has failed, it is immediately replaced by pulling a view update from the other alive nodes. Self-healing in Leader-based approach When a group leader abruptly crashes, one co-leader (for example, the one with the lowest identifier) becomes the new leader. Its first task consists in promoting a regular member as co-leader. Then, it transmits to the whole group the new leader identity and the new co-leader. The new leader will be contacted by leaders in the adjacent groups that also detect the leader failures, that will be made aware of the new leader identity.

Self-healing in Epidemic Approach

In epidemic-approach it is not easy to determine when a group has completely failed as nodes have in general divergent views about the group, predecessors and successors. We tolerate temporary situations in which the overlay is not consistent: for example two distinct groups for the same predicate exists in the tree and one of them does not point to any successor. However, this does not harm the connectivity of the tree, that is preserved at any time by the self-healing process, as shown by the simulation results in Section 5.2. The merge process described above eventually restores the overlay consistency.

Evaluation of DPS

Complexity Analysis

We discuss the scalability of DPS with respect to the message complexity. We also analyze the DPS reliability focusing on the probability that a subscriber interested in a particular filter receives events that match the filter. Moreover, we compare our different approaches (root-leader, root-epidemic, generic-leader, and generic-epidemic) with respect to these two complexity measures. Reliability. We determine the probability that a new subscriber interested in a filter receives a given concurrently published event. Let us consider a publication e and a concurrent subscription s such that e matches s filter. Let T s be the number of steps needed by s to find its similarity group, called the subscription turnaround time. Let T e be the number of steps e needs to reach the s group, called the publication turnaround time. Without compromising the generality, we focus on a single attribute (one tree in the DPS logical structure). Note that subscription s may not "see" event e if the time needed for subscriber s to find its group is greater than that by the publication s, i.e., T s > T e .

In root-based DPS, T s and T e are very close since both s and e start at the root of the tree and subscriptions have a higher priority over publications for being processed. Thus subscriptions issued concurrently to events are aware of these events if these events match the subscription filter.

In generic DPS, both T s and T e depend on the chosen contact point. Hence, it may happen that concurrent publications/subscriptions have different turnaround times. Let p i be the probability to choose a contact point on the i level of the tree and let s k be the probability that the similarity group of subscription s is on the level k. T s is greater than T e if the number of steps between s contact point and s similarity group is greater than the number of steps between e contact point and s similarity group. More precisely, the probability p that s does not see e is the probability that s contact point is at level i, e contact point is at level j, and s similarity group is at level k, with i < j < k. Formally, p = i<j<k p i p k s k . Among f events published concurrently with a new subscription, such that all the f events match the subscription filter, only a fraction f (1p) are received by the subscriber. Clearly, the root-based DPS causes fewer lost events than the generic DPS scheme, and thus, is more reliable.

Message complexity

We study the number of messages sent by the proposed algorithms. We focus only on one tree in the logical structure. Let h be the depth of the tree, S i the maximal size of a group at level i of the tree, k the number of infected neighbors at each round of the epidemic algorithm, and k the number of nodes contacted on the next level during the epidemic propagation along the tree.

Let us first consider the leader-based communication. In root-based scheme, the maximal number of messages corresponds to the traversal of a branch in the tree. Formally, the number is equal to i=0,(h-1) S i + (h -2). If S is the maximal size of a group, then the maximal number of messages is h(S + 1) -2. In generic-based scheme as the contact point may be any node in the tree, we need to consider that an event may traverse, in the worst case, the current branch up to the root and the other subtree from the root down to the bottom. The maximal number of messages is then 2h(S + 1) -4.

Let us now consider the epidemic-based communication. The root-based scheme produces in the worst case kS 0 + kk i=1,(h-1) S i +k (h-2) messages. If S is the maximal size of a group, the maximal number of messages is then

kS(1 + k (h -1)) + k (h -2). Similarly, the Generic based scheme produces 2(kS(1 + k (h -1)) + k (h -2)).

Simulation of DPS

In this section, we present the results of an experimental evaluation of our system performed using an event-based simulator we developed. The aim of the simulation is threefold: i) supporting the basic motivation behind the DPS overlay, i.e., efficient content-based filtering; ii) showing the practical feasibility of our approach and iii) showing that self-* properties can be achieved in a scalable manner without introducing serious (e.g., exponentially growing) overheads on message delivery. Following this direction, we compare all the combinations of the approaches presented in the paper. Simulation Context. The simulation is cycle based. The workload is characterized by the number and arrival/departure pattern of publishers and subscribers and by the distribution of publications and subscription they issue. Each experiment uses a different workload. Heartbeatbased failure detection between neighbors and recovery mechanism are implemented, with failure detection interval varying randomly from 10 to 25 steps. False Positives. First we concentrate on supporting our claim about the beneficial effect of the DPS organization on event dissemination. For each simulation run, we first issued 10,000 subscriptions (one per node) to build the over- lay and then we issued 10,000 events2 . The approach is generic, leader-based (not influencing results). We compute the number of visited nodes per event diffusion, evaluating the number of false positives. The overall number of messages is not considered in this experiment, nor failures and message losses. As the number of false-positives strongly varies according to the workload used, we considered a variety of synthetic workloads in order to cover a representative spectrum of different realistic situations. Synthetic workloads are mostly used in pub/sub simulation studies [START_REF] Carzaniga | Design and Evaluation of a Wide-Area Notification Service[END_REF][START_REF] Gupta | Meghdoot: Content-based publish:subscribe over p2p networks[END_REF], while a trace of real-world data is used at the best of our knowledge only in [START_REF] Wang | Subscription Partitioning and Routing in Content-based Publish/Subscribe Networks[END_REF]. Values for each attribute in subscriptions and events are generated by varying the following parameters: type (integer or string), distribution of values (uniform or zipf), average range size (for numerical subscriptions), percentage of equality predicates. Values for string attributes are chosen in a dictionary of 500 values. Details of the workloads are depicted in Table 1. Workload 1 uses distributions that have been discovered in [START_REF] Wang | Subscription Partitioning and Routing in Content-based Publish/Subscribe Networks[END_REF] to model real-world pub/sub data of a stock exchange application. Workload 2 models a multi-player game where players subscribe to events occurring in zones of a bidimensional game plane, whose size can be also very large thus generating a large number of matches. Finally, Workload 3 models an alert monitoring application, where subscriptions are concentrated on a restricted set of critical values and the overall number of matches is very low. Table 1 shows for each workload the percentage of contacted nodes and of matching nodes with respect to the total number of nodes, on average over the number of events, when using all the three workload types. The number of false positives is shown as well. In overall, we observed that DPS allows to cut the number of the visited nodes with respect to a broadcast by at least of the 45%, by a 70% on average, up to the 87% in more realistic situations. The number of false positives falls below an acceptable value of 30%, almost reaching 10% for the realistic workload. In the following sets of simulations, only workload 2 is used, in order to test only conditions which are less favorable for our system (i.e., more false positives). Again, we point out that with workloads based on a larger number of attributes, false positives are more likely to occur. Dependability. In these experiments, we test the ability of the system in delivering messages despite node failures. We built two different scenarios, where the system initially contains 1,000 nodes and the execution is 3,000 steps long. All nodes subscribe to three distinct subscriptions (different for each node) 3 . In the first scenario, node failures are uniformly distributed in time, with a frequency of 1/p, with p varying between 0.01 and 0.25 resulting, at the end of the simulation, in a number of nodes in the system which is, on an average, 97% to 25% of the initial nodes. This scenario tests a realistic situation where nodes disappear independently and in an unpredictable manner. A new event is published every 10 steps. In the second scenario, execution is divided into three phases. Nodes do not fail until step 1,000. Then one node fails every two steps between steps 1,000 and 2,000. From that point onwards, the system executes normally without failures all the way to the end of the execution. This scenario tests the recovery capabilities of the system after a large number of concurrent node failures. In both cases, we measure the ratio of correctly delivered events, i.e., the percentage of published events that reaches a node with a matching subscription.

Figure 3(a) shows the results of the first scenario. In all the approaches the system can reach a number of delivered events which is at least 80%, also when most of the nodes have failed. This is obtained with the leader-based approach, which is as expected the least 'robust'. Increasing the number of co-leaders may offer a way to further increase this figure. The epidemic scheme confirms the expected higher number of delivered events than the leaderbased approach. In particular, with epidemic, k=2, the ratio is greater than 0.97 even with a significant probability of failures. Results of the second scenario are exhibited in Figures 3(b), where the ratio of delivered messages is still high as events are delivered in more than 95% of cases. This curve also show that the system is able to self-recover as the ratio quickly grows back to 1 after step 2,000 in all cases. Scalability. We tested the ability of the system to scale by measuring the load managed by nodes when propagating events and subscriptions as the size of the system grows. In this scenario, the system initially contains 1,000 nodes.

A new node enters the system every two steps and immediately emits a new subscription. Publications are produced at a regular rate along system execution (10 new events every 100 steps). Figures 3(c) and 3(d) provide the results for this scenario in leader-based and epidemic configurations using root-based traversal 4 . The two plots report the time vs. the number of messages sent by a node per each event.

Figures 3(c) refers to the median node, defined as the node that sends less messages than half of the nodes and more messages than the other half. Figures 3(d) refers to the most overloaded node. The two plots show that in general the number of messages per event does not increase with the number of nodes, confirming the overall scalability of our approach. The only exception is the most overloaded node in the leader-based approach which has to handle more messages as system grows, because the size of the groups increases accordingly.

Leader vs. Epidemic

In the following experiments, we compare the behavior of the different approaches for implementing DPS while increasing the load at each node. Experiments are conducted in the following scenario: the number of nodes is 1,000, and each node emits regularly a new subscription and a new publication. Publications are produced at a rate of 10 new events every 100 steps, while a new subscription is produced regularly every 300 steps. Hence, the number of subscriptions per node ranges from 0 to 10 (maximum 10,000 4 Experiments performed using generic approach returned almost overlapping curves, that are not reported for the sake of readability in total). We measure the number of incoming and outcoming messages on the most loaded and median nodes, respectively, sampled during a period of 100 steps. Messages include the ones due to publication (10 events), subscription, and management of the overlay. Results were produced with a root-based approach for tree traversal and are presented in Figures 3(e) and 3(f).

Incoming Traffic. As expected, in epidemic communication the overall number of processed messages is in general higher than in leader-based because while in leaderbased approach, all events are received by the corresponding recipients only once, in the epidemic approach, some redundant messages are received. The difference remains constant when the number of subscriptions increases as it is only due to event delivery. The overall increase is due to the fact that groups become more populated. The median node in the leader-based scheme is only a receiver of the events. So, the received messages practically remain constant, growing only slightly because each node receives more matching events. On the contrary, in the epidemic approach, each node in the group is involved in overlay management. Besides processing the events, it also receives requests from the predecessor groups that grow as subscriptions grow. However, the increase in the number messages is much slower wrt the increase in the subscriptions. Again, the message redundancy motivates the higher number of received messages in the epidemic-based approach.

Outgoing Traffic. The drawback of the leader-based approach is evident when considering the outcoming traffic per node. The number of messages sent by the leader highly increases with subscriptions, following the increasing size of the groups and the higher number of recipients per event. Moreover, the load is highly unbalanced, with the median node showing no sending activity. As expected, the load is more balanced in the epidemic approach, because neighbors are distributed among the nodes in a group. However, we still experience a difference between the most overloaded node and the median, because the first nodes to join a group are more likely to be the contact nodes of numerous predecessors and successors. However, the most overloaded node in the epidemic approach handles less than half of the messages in the leader-based, although the overall number of processed messages is higher in the epidemic, confirming better load-balancing.

Root vs. Generic

The results of the comparison between root-based and generic approach, presented in Figure 3(g), were obtained in the same scenario as the preceding experiment 5 . Incoming Traffic. The most overloaded node in the rootbased approach is obviously the owner of the attribute. As the number of subscriptions increases, the number of messages it should deal with also increases. The generic approach effectively manages to distribute the incoming load among nodes, maintaining an almost constant number of messages at higher load. Note that the subscriptions influence the incoming traffic more than the outcoming traffic. This indicates the positive effect of the generic approach on the subscription process. Outgoing Traffic. These experiments reveal few differences between the two approaches. This can be explained by considering that the outgoing messages in the leaderbased approach are mainly due to the events. The most overloaded node in both cases corresponds to the leader of the bigger group. As the number of subscriptions increases, the size of the group and, subsequently, the leader outgoing traffic increase as well. Using the leader-based approach, in both cases, the median node does not send any messages.

Conclusion and Discussion

We have presented DPS, a distributed reliable and scalable content-based publish/subscribe system that exhibits self- * characteristics. We have proposed different methods of diffusion of subscriptions and publications that can be combined to obtain four different implementations of the system. Based on the simulation results, we can conclude that the leader-based approach is more suitable for a relatively small set of nodes that are less prone to failures. On the other hand, the epidemic-approach provides higher dependability, better scalability, and load balancing at the cost of higher message complexity. As for the tree traversal strategies, the generic approach is more suitable for the subscription process as it better distributes the load. On the contrary, the publication process benefits from the rootbased approach that obviously provides lower latency. The possibility of choosing different implementations makes the proposed system very versatile, so it can be deployed in many applications (e.g., virtual worlds, virtual games, emarket, etc.). As a future research direction, we intend to explore the evaluation of DPS in other specific contexts, such as sensor networks.

Figure 3 .

 3 Figure 3. Experimental Results

Figure 1. Logical Trees defined

  as a tuple AF i = (name i Op i c i ) where name i is the name of the attribute, Op i is an operator, and c i is a constant value. The operator Op i can be chosen from a set of basic operators that depends on the attribute type. For example, possible operators for numerical attributes are {=, <, >}, while string attributes can support prefix, suffix and substring wildcards. Complex filters can be expressed as the conjunction of two or more basic operators. For example, a range filter for an attribute a of the form c 1 < a < c 2 can be obtained as the conjunction of the two predicates AF 1 = (a > c 1 ) and AF 2 = (a < c 2

	s 3 : b>3 ! c=abc s 0 : a>2 ! b>0 s 1 : a>2 ! a<500 s 2 : a>5 ! b<2			a	a>2 s 1 s 0		b	s 6 b<7	c	s 7 c=ab*
	s 4 : a<4 ! b>20 s 5 : a=4 ! c=abc s 6 : a<3 ! b>3 ! b<7 s 7 : b>3 ! c=ab*		a>3	s 11		a<20 s 8	b<5	s 10	s 4 b>20	s 3	c=abc
	s 10 : a>50 ! b<5 s 8 : a>2 ! a<20 ! c=a* s 9 : a<11	a>5	s 2		s 5 a=4	s 9 a<11
	s 11 : a>3 ! b<50

Table 1 . False Positives Experiment: Workload details and Results

 1

		Attr.	Ev. Distr.	Sub. Distr.	Range Size	Eq. Perc.	Matching	Contacted	False Positives
	Workload 1	num	unif	zipf	10%	50%	2.37%	13.56%	11.19%
		string	unif	zipf		50%
	Workload 2 Workload 3	2 × num 3 × num	unif zipf	unif zipf	50% 20%	0% 20%	25.13% 0.42%	54.74% 17.15%	29.61% 16.73%

Connections between trees are not shown in figures for clarity

The number of events and subscription does not influence the results and is chosen as a sufficiently large sample

Increasing the number of subscriptions per node does not change the nature of the results in this experiment

* Antonino Virgillito is partially supported by project MAIS, funded by Italian MIUR. Work was done while author was at IRISA, Rennes.


Jonathan Passerat-Palmbach

Mathieu Leclaire

Romain Reuillon

Zehan Wang

Daniel Rueckert

OpenMOLE: a Workflow Engine for Distributed Medical Image Analysis

Keywords: Distributed Computing, Grid Computing, Workflow, Reproducibility, Medical Image Analysis, OpenMOLE

This works demonstrates how the OpenMOLE platform can provide a straightforward way to distribute heavy workloads generated by medical imaging analysis. OpenMOLE allows its users to benefit from a large set of distributed computing infrastructures such as clusters or computing grids, no matter the kind of application they are running. Here we extend the OpenMOLE tools to two new cluster job schedulers: SLURM and Condor. We also contribute to the Yapa packaging tool to support the widely spread virtual environment package from the Python programming language. Our test case shows how our developments allow a medical imaging application to be distributed using the OpenMOLE toolkit.

Introduction

Medical image analysis can be very computationally expensive. General computation times have increased as data sets have grown and become more complex to process. At the same time, recent languages such as Python have spread in the community. They are easy to learn and simple to use. In the case of Python, a very thorough set of packages dedicated to scientific applications make it a first choice for many scientists. Still, as an interpreted language, it introduces an overhead at runtime.

These complex applications also come with numerous input parameters that can be tuned. In the search of the ideal parameter set among all the possible combinations, it is ideal to match all these different parameters to each of the images from the data set. If we think of the processed image as just another parameter taking different values, this leads to an overwhelming number of potential combinations. Testing all these combinations with the studied application becomes unmanageable on a regular desktop platform.

Two options can lead to performance improvements for this problem. The first strategy is to optimize and/or parallelize the base application. This is obviously a very interesting approach, but it can be difficult to obtain decent improvements without being an expert in this domain. Also, this does not reduce the number of parameter combinations to execute.

One other approach is to use distributed computing platforms to spread the workload across several machines. In an ideal world, the time required to process the whole experiment would be equivalent to the execution time of the application fed with a single instance of parameters set. Please note that this approach is not incompatible from any attempt to parallelize or optimize the base application.

This work focuses on making distributed computing available in the most straightforward way to the medical imaging community. Depending on the applications, several problems might arise when attempting to distribute the execution. Software tools can help scientists overcome these hindrances. Our study describes the input of such a tool called OpenMOLE and its software ecosystem.

OpenMOLE is a workflow distribution platform which aims at offering scientists from any field a tool to model their experiments as workflows, and then distribute their execution remotely to spread the workload. Compared to other workflow processing engines, it relies on a zero-deployment approach to a wide range of distributed computing environments. OpenMOLE also encourages the use of software components developed in heterogeneous programming languages and enable its user to easily replace the elements involved in the workflow. Workflows can be designed using either a GUI, or a Scala DSL which exposes advanced workflow design constructs. For more details regarding the core implementation and features of OpenMOLE, the interested reader can refer to [START_REF] Reuillon | Declarative task delegation in OpenMOLE[END_REF], Reuillon et al., 2013] and to the public Git repository hosting OpenMOLE's source code1 .

In this paper, we first detail the problems faced by the medical imaging community to effectively distribute an application. Then, we present how the tools from the OpenMOLE ecosystem can answer these problems. The next section addresses changes to OpenMOLE tools induced by challenges related to software configurations frequently encountered in medical imaging applications. We finally present a test case showing how an actual medical imaging application has been successfully distributed using OpenMOLE.

The Challenges of Distributing Applications

Let us consider all the dependencies introduced by software bundles explicitly used by the developer. They can take the form of shared libraries for binary applications or packages for Python.

These software dependencies become a problem when distributing an application, as it is unlikely that a large number of remote hosts will be deployed in the very same configuration as a researcher's desktop computer. If a dependency is missing, the remote execution will simply fail on the remote hosts where the requested dependencies are not installed.

An application can also be prevented from running properly due to incompatibilities between versions of the deployed dependencies. This case can lead to silent errors, where a software dependency would be present in a different configuration and would generate different results for the studied application. This problem breaks Provenance, a major concern of the scientific community [START_REF] Miles | The requirements of using provenance in e-science experiments[END_REF], MacKenzie-Graham et al., 2008]. Provenance criteria are satisfied when an application is documented thoroughly enough to be reproducible. This can only happen in distributed computing environments if the software dependencies are clearly described and available.

Some programming environments provide a solution to these problems. Compiled languages such as C and C++ offer to build a static binary, which packages all the software dependencies. Some applications can be very difficult to compile statically. A typical case is an application using a closed source library, for which only a shared library is available.

Another approach is to rely on an archiving format specific to a programming language. The most evident example falling into this category are Java Archives (JAR) that embed all the Java libraries an application will need.

The next section will detail how OpenMOLE tackles these problems in three steps.

Harnessing OpenMOLE for Medical Image Analysis

OpenMOLE shows several main advantages with respect to the other workflow management tools available. The interested reader will find thorough surveys describing the scientific workflow processing tools in [Barker andVan Hemert, 2008, Mikut et al., 2013]. First, OpenMOLE distinguishes as a tool that does not target a specific scientific community, but offers generic tools to explore large parameter sets.

Second, while OpenMOLE offers a GUI to design workflows as most workflow management systems, it also features a Domain Specific Language (DSL) to describe the workflows. According to [Barker and Van Hemert, 2008], workflow platforms should not introduce new languages but rely on established ones. OpenMOLE's DSL is based on the high level Scala programming language [START_REF] Odersky | An overview of the scala programming language[END_REF]. Section 3.2 details the role played by the DSL to establish the Provenance of the workflow.

Finally, OpenMOLE features a great range of platforms to distribute the execution workflows, thanks to the underlying GridScale library2 . GridScale is part of the OpenMOLE ecosystem and acts as one of its foundation layers. It is responsible of accessing the different execution environments. The last release of OpenMOLE can target SSH servers, multiple cluster managers and computing grids ruled by the gLite/EMI middleware.

In this section, we describe the three tools from the OpenMOLE ecosystem that answer the problems evoked in Section 2. These three tools refer to three simple steps to explore a set of parameters and distribute the resulting workload.

Packaging the application with Yapa

The first step in order towards spreading the workload across heterogeneous computing elements is to make the studied application executable on the greatest number of environments. We have seen previously that this could be difficult with the complex software environments entanglements available nowadays. For instance, a Python script will run only in a particular version of the interpreter and make use of binary dependencies. The best solution to make sure the execution will run as seamlessly on a remote host as it does on the desktop machine of the scientist is to track all the dependencies of the application and ship them with it on the execution site.

The OpenMOLE ecosystem provides this feature through a tool called Yapa3 . Yapa relies on the CDE (Code, Data, and Environment packaging) application [Guo, 2012] to create archives containing all the items required by an application to run on any recent Linux platform.

CDE tracks all the files that interact with the application and creates the base archive. Yapa completes the package by adding specific customizations related to the integration of the application within an OpenMOLE workflow. In OpenMOLE, workflows are mainly composed of tasks. Yapa creates the task corresponding to the packaged application, simply by studying the output of CDE. The result is a ready to run package containing the application and all its dependencies, independent from the configuration of the host executing it. As an OpenMOLE task, the generated package is ready to be added to the OpenMOLE scene to be integrated in a workflow.

In our case, we extended the scope of Yapa to enable it to correctly handle Python applications using the Virtual Environment4 package. Virtual Environment is quite common in Python developments as it allows to install and configure a Python environment on a system, without interfering with the main installation. This way, different versions of the same Python package can cohabit on the same machine without impacting the execution of other Python scripts.

The problem is, Virtual Environment sets up the execution environment in a specific way to isolate the application. This behaviour conflicted with Yapa which could not supervise the whole execution in this case. Yapa returned prematurely, preventing CDE to capture all the dependencies. Our study has raised this problem and proposed a correction that now enables Yapa to package correctly Python applications using the Virtual Environment package. The updated release is available from Yapa's source code repository.

The only constraint regarding Yapa is to create the archive on a platform running a Linux kernel from the same generation as those running on the targeted computing elements. As a rule of thumb, a good way to ensure that the deployment will be successful is to create the Yapa package from a system running Linux 2.6.32. Many HPC environments run this version, as it is the default kernel used by science-oriented Linux distribution, such as Scientific Linux and CentOS.

Describing the application as an OpenMOLE workflow

Scientific experiments are characterized by their ability to be reproduced. For medical image analysis applications, this implies capturing all the processing stages leading to the result. Many execution platforms introduce the notion of workflow to do so [Barker andVan Hemert, 2008, Mikut et al., 2013]. Likewise, OpenMOLE manipulates workflows and distribute their execution across various computing environments. Reproducibility becomes a concern when a scientist wants to reproduce a given workflow on an environment different from the original computing platform. With classic workflow descriptions, this process can be tedious since in spite of some efforts of standardization [Barker and Van Hemert, 2008], no standard workflow description has been adopted yet. It is then difficult to provide the right Provenance information that will enable workflows reproducibility.

Two choices are available when it comes to describe a workflow in Open-MOLE: the Graphical User Interface (GUI) and the Domain Specific Language (DSL). Both strategies result in identical workflows. They can be shared by users as a way to reproduce their execution. In terms of Provenance information, the DSL is more relevant as its self-explicit format can be read apart from OpenMOLE.

OpenMOLE's DSL is based upon the Scala programming language, and embeds new operators to manage the construction and execution of the workflow. The advantage of this approach lies in the fact that workflows can exist even outside the OpenMOLE environment. As a high-level language, the DSL can be assimilated to an algorithm described in pseudocode, understandable by most scientists. Moreover, it denotes all the types and data used within the workflow, as well as their origin. This reinforces the capacity to reproduce workflow execution both within the OpenMOLE platform or using another tool.

Running the workflow

With the studied application packaged and the associated workflow described, there is left to determine the execution environment. OpenMOLE enables delegating the workload to a wide range of HPC environments including remote servers (through SSH), clusters (supporting the job scheduler PBS) and computing grids running the gLite/EMI middleware. For the purpose of this study, we also made available plugins for SLURM and Condor, two other job schedulers for clusters.

Submitting jobs to distributed computing environments can be complex for some users. This difficulty is hidden by the GridScale library from the Open-MOLE ecosystem. GridScale provides a high level abstraction to all the execution platforms mentioned previously.

When GridScale was originally conceived, a choice was made not to rely on a standard API (Application Programming Interface) to interface with the computing environments, but to take advantage of the command line tools available instead. As a result, GridScale can embed any job submission environment available from a command line. From a higher perspective, this allows Open-MOLE to work seamlessly with any computing environment that the user can access.

Users are only expected to select the execution environment for the tasks of the workflow. This choice can be guided by two considerations: the availability of the resources and their suitability to process a particular problem. The characteristics of each available environments must be considered and matched with the application's characteristics. Depending on the size of the input and output data, the execution time of a single instance and the number of independent executions to process, some environments might show more appropriate than others.

In the particular case of medical imaging, the European Grid Initiative (EGI) gathers a pool of resources under the name Biomed. Biomed is a Virtual Organization (VO), i.e.: a subset of a computing grid gathering users and resources sharing the same interests. This infrastructure connects computing clusters from universities and research laboratories across Europe to offer more than 300,000 CPU cores to its members. This large scale computing environment is supported by OpenMOLE.

At this stage, OpenMOLE's simple workflow description is extremely convenient to determine the computing environment best suited for a workflow. Switching from one environment to another is achieved either by a single click (if the workflow was designed with the GUI) or by modifying a single line (for workflows described using the DSL).

4 Test Case: Distribution of a Patch-Based Segmentation Application

Our test case involves a patch-based segmentation application that implements a label propagation approach. To do so, it uses relative geodesic distances to define patient-specific coordinate systems as spatial context [START_REF] Wang | Geodesic patch-based segmentation[END_REF].

For the sake of our tests, we focus on running this application to perform multiorgan segmentation of abdominal CT images.

The workflow we describe in OpenMOLE studies a set of 150 different input images. The resulting workflow was distributed using a cluster managed using the SLURM job scheduler, and on the European Grid Infrastructure's Biomed VO, which is managed by the gLite/EMI middleware.

Depending on the input image, the processing time for a single image ranges from approximately 10 to 24 hours. The application is written in Python and uses common packages such as SciPy and NumPy. The Python configuration is handled through the Virtual Environment package.

Packaging the application using Yapa is straightforward and as explained earlier, does not impact the original command line, as shown in Listing 1. In this example, the application's parameters are set to arbitrary values selected from the set of existing combinations.

1 java -jar yapa.jar -o /tmp/package.yapa -c "python ./scripts/ abdominalwithreg.py --spatialWeight 7 --queryDilation 4 --preDtErosion 2 --atlasBoundaryDilation 6 -k 40 --numAtlases 50 --patchSize 5 --spatialInfoType coordinates --resLevel 3 --numProcessors 1 --dtLabels 0 3 4 7 8 --savePath /vol/bitbucket/jpassera/PatchBasedStandAlone/ AbdominalCT/Results --transformedImagesPath /vol/bitbucket /jpassera/AbdominalCT/TransformedImages --transformedLabelsPath /vol/bitbucket/jpassera/AbdominalCT/ TransformedLabels --transformedGdtImagesPath /vol/ bitbucket/jpassera/AbdominalCT/TransformedGdtImagesPath --transformedDtLabelsPath /vol/bitbucket/jpassera/ AbdominalCT/TransformedDtLabels --fileName nusurgery001 .512.nii.gz"

Listing 1: Packaging an application with Yapa

The resulting package contains all the software dependencies and input files required for the application to work correctly. It forms an OpenMOLE task that is ready to be part of a workflow. We can now describe this workflow to explore the parameter set of 150 images, and define the inputs and outputs of the application task. The resulting workflow is presented in Listing 2. The first element introduced is an ExplorationTask. This is an OpenMOLE predefined task that establishes the list of different parameters combinations that can be created from the set of parameters. As we limit this example to the exploration of the whole set of images, the ExplorationTask will generate a list of the input images file names.

A SystemExecTask embeds the main component of the workflow: the segmentation application packaged with Yapa. Several notions appear when describing this task as it takes inputs, outputs and requires resources. The Open-MOLE DSL makes attaching all these elements to the task crystal clear to the external reader, as the associated operations are respectively addInput, addOutput and addResource.

At this stage, we have two tasks on the scene: the ExplorationTask generating the different combinations of input parameters and the SystemExecTask, embedding the actual application. The final part of the workflow connects these tasks and instantiates them on a computing environment.

Links between two tasks are called transitions in the OpenMOLE terminology. In our case, an exploration transition connects the tasks. The OpenMOLE DSL describes this transition using the unfaltering fork symbol (-<). This symbol represents the multiple instances of the SystemExecTask created to process each parameter combination generated.

Last but not least, the SystemExecTask benefits from a specific care as its execution is delegated to a remote execution environment. This is achieved using the on keyword, recalling that a task is running on a particular environment. Brackets around this statement ensure that only this task is subject to remote execution, and the ExplorationTask remains in the local environment. This workflow delegates the execution to the EGI computing grid and more particularly to its Biomed VO. As shown in comments of Listing 2, a single word in the execution statement would delegate the task to another previously defined execution environment.

In this test case, we have chosen to study the exploration of a single parameter: the input image. Now that the application is packaged, and the workflow described, it is easy to extend this exploration to the whole set of parameters. The heavy computational workload resulting from such a workflow would only suit a large distributed computing environment such as the European Grid Infrastructure.

Conclusion

In this paper, we have shown how to delegate the execution of medical imaging applications running in a Linux platform to a distributed computing infrastructure. To do so, we have added new features to the OpenMOLE ecosystem, and shown its relevancy to manage this kind of experiments.

The Yapa packaging application can now handle complex Python setups using the Virtual Environment package. Regarding the available environments, the SLURM and Condor job schedulers are now supported by OpenMOLE, via the development of two new plugins for the GridScale library.

We have designed a workflow to explore the parameters of a segmentation method implemented in Python. This workflow can now be reused by any scientist through OpenMOLE, in order to reproduce the exploration of the same parameter set. This solution is extremely portable since the application distributed through OpenMOLE has been packaged with Yapa and can thus be executed on any platform running 2.6.32 Linux kernel or a more recent version.

This work shows that the genericity of the OpenMOLE platform platform does not prevent it tackle efficiently the distribution of medical imaging applications. Also, the free and open source licence of the tools belonging to the OpenMOLE ecosystem allows anyone to contribute to the project and extend the support to any missing computing environment.

Future works regarding the OpenMOLE platform will target the delegation of workflows to federated heterogeneous distributed computing environments.

  1 import org.openmole.plugin.task.systemexec._ 2 import org.openmole.plugin.hook.file._ 3 import org.openmole.plugin.domain.collection._ 4 import org.openmole.plugin.domain.file._ 5 import org.openmole.plugin.environment.glite._ 6 7 val imageID = Prototype[String]("imageID") 8 val idsList = List( 1 to 200 by 2, 301 to 519 by 2 ).flatten.map ("%03

	24 "cde11_zehan/cde-root/vol/bitbucket/jpassera/
		PatchBasedStandAlone"
	25 )
	26
	27 // the packaged application is a resource of the task
	28 cTask addResource "/data/cde11_zehan"
	29 cTask addInput imageID
	30
	31 // imageID must be defined as output to be reused in Hook
	32 val resultArchiveFile = Prototype[File] ("resultArchiveOut")
	33 cTask addOutput ("AbdominalCT/Results", resultArchiveFile)
	34 cTask addOutput imageID
	35
	36 // hooks allow result files retrieval
	37 val resultHook = CopyFileHook(resultArchiveFile, "results_biomed
		/${imageID}")
	38	d" format _)
	9 39 // definition of the Biomed VO environment
	10 // construct the parameter set 40 GliteAuthentication() = P12Certificate(encrypted, "/homes/
	11 val exploIDsTask = ExplorationTask ( jpassera/.globus/grid_certificate_uk_2014.p12")
	12 "exploIDs", 41 val biomed = GliteEnvironment("biomed")
	13 Factor( 42
	14 43 // connect the tasks with transitions and run the workflow imageID,
	15 44 val ex = exploIDsTask -< (cTask on biomed hook resultHook) idsList toDomain
	16 )	toExecution
	17 ) 45 ex.start
	18 Listing 2: Workflow describing the delegation of the studied application to the 19 // the SystemExecTask mimics the command line, but runs from the Yapa archive Biomed VO of the EGI computing grid
	20 val savePath = "/vol/bitbucket/jpassera/PatchBasedStandAlone/
		AbdominalCT/Results"
	21 val cTask = SystemExecTask(
	22 "myRunTask",
	23 "./python.cde ./scripts/abdominalwithreg.py --spatialWeight
		7 --queryDilation 4 --preDtErosion 2 --
		atlasBoundaryDilation 6 -k 40 --numAtlases 50 --patchSize
		5 --spatialInfoType coordinates --resLevel 3 --
		numProcessors 1 --dtLabels 0 3 4 7 8 --savePath " +
		savePath + " --transformedImagesPath /vol/bitbucket/
		jpassera/AbdominalCT/TransformedImages --
		transformedLabelsPath /vol/bitbucket/jpassera/AbdominalCT
		/TransformedLabels --transformedGdtImagesPath /vol/
		bitbucket/jpassera/AbdominalCT/TransformedGdtImagesPath
		--transformedDtLabelsPath /vol/bitbucket/jpassera/
		AbdominalCT/TransformedDtLabels --fileName nusurgery${
		imageID}.512.nii.gz",

https://github.com/openmole/openmole

https://github.com/openmole/gridscale

https://github.com/openmole/yapa

https://github.com/pypa/virtualenv

Acknowledgments

The research leading to these results has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement n. 319456.