Keywords: Édition collaborative, Réplication optimiste, Réseaux pair-à-pair, Interception distribuée

UniWiki: Une architecture fiable et supportant le passage à l'échelle pour la distribution d'applications orientées wiki Résumé : L'utilisation grandissante des documents numériques soulève un besoin en de nouvelles architectures proposant une immense capacité de stockage tout en garantissant une haute disponibilité des données stockées. Bien que de nombreuses propositions aient été réalisées pour répondre à cette demande pour la distribution de données quasi-immuables, il n'existe pas ou peu de proposition qui s'intéresse à ce problème pour des données hautement dynamiques telles que les données gérées par les serveurs wiki. Dans cet article, nous proposons une architecture pair-à-pair pour la distribution et la gestion de contenu hautement dynamique. Cette solution repose sur une table de hachage distribuée combinée avec un mécanisme de réplication optimiste. Afin de valider cette proposition, nous présentons une implémentation réalisée en utilisant un canevas d'interception distribué qui permet d'une part de séparer les responsabilités de distribution, de réplication et de maintien de la cohérence, et également, d'intégrer notre approche de manière transparente aux serveurs d'applications wiki existants. Cette implémentation s'est montrée viable et efficace dans des scénarios d'expérimentation à large échelle.

Introduction

Peer to peer (P2P) systems, which account for a significant part of all internet traffic, rely on content replication at more than one node to ensure scalable distribution. This approach can be seen as a very large distributed storage system, which has many advantages, such as resilience to censorship, high availability, virtually unlimited storage space [START_REF] Androutsellis-Theotokis | A Survey of Peer-to-Peer Content Distribution Technologies[END_REF]. Currently, P2P networks mainly distribute immutable contents. We aim at making use of their characteristics for distributing dynamic, editable content. More precisely, we propose to distribute updates on this content and manage collaborative editing on top of such a peer to peer network. We are convinced that, if we can deploy a group editor framework on a P2P network, we open the way for P2P content editing: a wide range of existing collaborative editing applications, such as CVS and Wikis, can be redeployed on P2P networks, and thus benefit from the availability improvements, the performance enhancements and the censorship resilience of P2P networks.

Our architecture targets heavy-load systems, that must serve a huge number of requests. An illustrative example is Wikipedia [START_REF]Wikipedia, the online encyclopedia[END_REF], the collaborative encyclopaedia that has collected, until now, over 11,500,000 articles in more than 250 languages. It currently registers at least 350 million page requests per day, and over 300,000 changes are made daily [36]. To handle this load, Wikipedia needs a costly infrastructure [START_REF] Bergsma | Wikimedia architecture[END_REF], for which hundreds of thousands of dollars are spent every year. A P2P massive collaborative editing system would allow to distribute the service and share the cost of the underlying infrastructure.

Existing aproaches to deploy a collaborative system on a distribted network include Wooki [START_REF] Weiss | Wooki: a P2P Wiki-based Collaborative Writing Tool[END_REF], DistriWiki [START_REF] Morris | Distriwiki: A distributed peer-to-peer wiki network[END_REF], RepliWiki [START_REF]RepliWiki -A Next Generation Architecture for Wikipedia[END_REF], Distributed Version Control systems [START_REF] Allen | ClearCase MultiSite: Supporting Geographically-Distributed Software Development[END_REF][START_REF]Git -fast version control system[END_REF]37], DTWiki [START_REF] Du | Dtwiki: a disconnection and intermittency tolerant wiki[END_REF] and Piki [START_REF] Mukherjee | Piki -a peer-to-peer based wiki engine[END_REF]. Several drawback prevent these systems from being used in our target scenario. They either require total replication of content, requiring all wiki pages are replicated at all nodes, or do not provide support for all the features of a wiki system such as page revisions, or provide only a basic conflict resolution mechanism that is not suitable for collaborative authoring.

This paper presents the design and the first experimentations of a wiki architecture that:

• is able to store huge amounts of data,

• runs on commodity hardware by making use of peer to peer networks,

• does not have any single point of failure, or even a relatively small set of points of failure,

• is able to handle concurrent updates, ensuring eventual consistency.

To achieve these objectives, our system relies on the results of two intensively studied research domains, distributed hash tables [START_REF] Rowstron | Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems[END_REF] (DHT) and optimistic replication [START_REF] Saito | Optimistic Replication[END_REF]. At the storage system level, we use DHTs, which have been proved [START_REF] Ktari | Performance Evaluation of Replication Strategies in DHTs under Churn[END_REF] as quasi-reliable even in test cases with a high degree of churning and network failures. However, DHTs alone are not designed for supporting consistently unstable content, with a high rate of modifications, as it is the case with the content of a wiki. Therefore, instead of the actual data, our system stores in each DHT node operations, more precisely the list of changes that produce the current version of a wiki document. It is safe to consider these changes as the usual static data stored in DHTs, given that an operation is stored in a node independently of other operations, and no actual modifications are performed on it. Because the updates can originate in various sources, concurrent changes of the same data might occur, and therefore different operation lists could be temporarily available at different nodes responsible for the same data. These changes need to be combined such that a plausible most recent version of the content is obtained. For this purpose, our system uses an optimistic consistency maintenance algorithm, WOOT [START_REF] Oster | Data Consistency for P2P Collaborative Editing[END_REF], which guarantees eventual consistency, causal consistency and intention preservation [START_REF] Sun | Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems[END_REF].

To reduce the effort needed for the implementation, and to make our work available to existing wiki applications, we built our system using a distributed interception middleware (Damon [START_REF] Mondéjar | Damon: a decentralized aspect middleware built on top of a peer-to-peer overlay network[END_REF][START_REF] Mondéjar | Building a distributed AOP middleware for large scale systems[END_REF]). Thus, we were able to reuse existing implementations for all the components needed, and integrate our method transparently.

Section 2 presents approaches related to our proposition and analyzes their strong and weak points. In the same section, an overview of DHT characteristics and optimistic consistency maintenance algorithms is presented. The paper further describes, in Section 3, the architecture of the UniWiki system and its algorithms. An implementation of this system is presented in Section 4. In Section 5, a validation via experimentation on a large-scale scenario is demonstrated. The paper concludes in Section 6.

Related Work

Existing Approaches

One of the most relevant architectural proposals in the field of large-scale collaborative platforms is a semi-decentralized system for hosting wiki web sites like Wikipedia, using a collaborative approach. This design focuses on distributing the pages that compose the wiki across a network of nodes provided by individuals and organizations willing to collaborate in hosting the wiki. The paper [START_REF] Urdaneta | A decentralized wiki engine for collaborative wikipedia hosting[END_REF] presents algorithms for page placement so that the capacity of the nodes is not exceeded and the load is balanced, and algorithms for routing client requests to the appropriate nodes.

In this architecture, only the storage of content wiki pages is fully distributed. Client requests (both read and write) are handled by a subset of trusted nodes, and meta-functionalities, such as user pages, searching, access controls and special pages, are still dealt with in a centralized manner.

While this system can resist random node departures and failures (one of the inherent advantages of replication), it does not handle more advanced failures, such as partitioning, and performs poorly with respect to concurrent updates (since write are done on limited number of trusted nodes).

Approaches that relate more to the P2P model include:

• DistriWiki [START_REF] Morris | Distriwiki: A distributed peer-to-peer wiki network[END_REF], based on the JXTA™ [START_REF] Gong | JXTA: A Network Programming Environment[END_REF] protocol, provides a peer-to-peer wiki architecture, where each node represents a set of wiki pages stored on a user's computer. It concentrates on the communication aspect, but ignores wiki specific features, such as versioning, and does not solve the problem of merging concurrent contributions from different users.

• DTWiki [START_REF] Du | Dtwiki: a disconnection and intermittency tolerant wiki[END_REF] uses delay tolerant network (DTN) [START_REF] Fall | A Delay-tolerant Network Architecture for Challenged Internets[END_REF] as the basis for building a distributed and replicated storage mechanism, enabling offline work and access from terminals with intermittent Internet access.

• Piki [START_REF] Mukherjee | Piki -a peer-to-peer based wiki engine[END_REF] adapts Key Based Routing [START_REF] Dabek | Towards a Common API for Structured Peer-to-Peer Overlays[END_REF] and Distribute Hash Tables [START_REF] Rowstron | Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems[END_REF] (DHTs) to build its storage mechanism, where each node in the P2P network is responsible for storing a number of pages.

• Another approach [START_REF] Plantikow | Transactions for Distributed Wikis on Structured Overlays[END_REF] proposes the usage of DHTs as the underlying storage mechanism, backed by a safe distributed transaction manager based on Paxos, inheriting all the advantages of DHTs: quasi-reliable distributed storage, fault tolerance, censorship resilience.

These systems concentrate on the communication and replication aspects, but do not properly address concurrent updates. They either do not consider the problem, or take a transactional approach where only one user can successfully save his changes. Both approaches are clearly not adapted to collaborative authoring since some user's contributions might be lost.

Concurrent editing can be identified as the main concern of other systems:

• RepliWiki [START_REF]RepliWiki -A Next Generation Architecture for Wikipedia[END_REF] aims at providing an efficient way of replicating large scale wikis like Wikipedia, in order to distribute the load and ensure that there is no single point of failure. The central part of the RepliWiki is the Summary Hash History (SHH) [START_REF] Kang | Summary Hash History for Optimistic Replication of Wikipedia[END_REF], a synchronization algorithm that aims at ensuring divergence control, efficient update propagation and tamper-evident update history.

• Wooki [START_REF] Weiss | Wooki: a P2P Wiki-based Collaborative Writing Tool[END_REF] is a wiki application built on top of a unstructured peer-to-peer network. Propagation of updates among peers is accomplished by the means of a probabilistic epidemic broadcast, and merging of concurrent updates is under control of the WOOT [START_REF] Oster | Data Consistency for P2P Collaborative Editing[END_REF] consistency maintenance algorithm. This algorithm ensures convergence of content and intention preservation [START_REF] Sun | Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems[END_REF] -no user updates are lost in case of merging.

• Git [START_REF]Git -fast version control system[END_REF], a distributed version control system (DVCS) where the central source repository is replaced by a completely decentralized peer to peer network, stands as the underlying storage mechanism for several wiki systems: git-wiki, eWiki, WiGit, Ikiwiki, ymcGitWiki. The advanced merging capabilities of Git make these wiki systems suitable for offline and distributed content authoring. Unfortunately, DVCSs ensure only causal consistency, which means convergence of replicated content is not guaranteed.

Unlike the previous approaches, the latter handle concurrent updates efficiently. However, by employing total replication, where all nodes contain copies of the whole data, they limit their scalability since the number of possible "donors" is drastically reduced by the need to be powerful enough to host the entire wiki system. They are suitable for smaller wikis, and can apply to the scenario of collaborative writing in mobile environments.

Background

Distributed Hash Tables (DHT), one of the most well discussed topics regarding P2P systems, provide a simple distributed storage interface, with decentralization, scalability and fault tolerance as its main properties.

Throughout the last decade, several architectures were proposed, each with its various strong points. The most notable are Chord [START_REF] Stoica | Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications[END_REF], one of the favorites in the academic/research environment, Pastry [START_REF] Rowstron | Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems[END_REF], frequently used in practice, Tapestry [START_REF] Zhao | Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing[END_REF], CAN [START_REF] Ratnasamy | A Scalable Content-addressable Network[END_REF] and Kademlia [START_REF] Maymounkov | Kademlia: A Peer-to-Peer Information System based on the XOR Metric[END_REF]. All DHT systems have in common a simple map storage interface, allowing to put(key, value) and get(key) back values from the storage. Beyond this common ideology, the implementations have critical differences. While some allow storing just one value for each key, others maintain a list of values, which is updated on each call of put. Several implementations even have an expiration mechanism, where a value is associated with a key for a limited period of time, after which it is removed from the list of values for that key.

DHTs have been successfully used in peer to peer applications, not only in file-sharing programs like BitTorrent [START_REF] Pouwelse | The Bittorrent P2P File-Sharing System: Measurements and Analysis[END_REF], but also inside critical systems such as the storage mechanism of the heavily-accessed Amazon [START_REF] Decandia | Dynamo: Amazon's Highly Available Key-Value Store[END_REF].

Although DHTs have been popular long before any of the distributed wiki systems have been proposed, few architectures employ them in wiki applications. This is a natural consequence of the fact that only static content can be reliably stored in a DHT, or at most content with infrequent updates originating from one point. Decentralized concurrent updates could create inconsistent states and cause loss of content.

A control mechanism suitable for maintaining consistency of shared data in collaborative editing is provided by the operational transformation approach [START_REF] Ellis | Concurrency control in groupware systems[END_REF][START_REF] Sun | Operational transformation in real-time group editors: Issues, algorithms, and achievements[END_REF]. Instead of sharing the actual document, the peers maintain the list of actions that users performed to create that content. During reconciliation phases, the concurrent actions are transformed regarding each other in order to compute a document state that combines modifications performed by users. This combination is computed in such a way that it ensures convergence of copies regardless of the order in which operations are received. In comparison, traditional consistency algorithms used in version control systems -distributed or not -ensure only causal consistency: all actions are seen in the same order they have been performed, but do not guarantee convergence of copies in presence of concurrent actions.

Moreover, OT approaches ensure an additional correctness criteria called intention preservation [START_REF] Sun | Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems[END_REF]. Intention preservation guarantee that effect of operations are preserved while obtaining convergence. User contributions are mixed in order to compute the convergence state rather than being simply discarded.

Any kind of content can be managed using operational transformations, not only linear text, as long as the correct transformations are defined. The difficulty resides in finding these transformations. Several algorithms have been proposed based on this approach, working on environments with different specifics. Unfortunately, most of them require either a central server or the use of vector clocks in order to ensure causality between updates. These requirements limit the potential scalability of OT-based systems.

Another approach is WOOT, (WithOut Operational Transformation) [START_REF] Oster | Data Consistency for P2P Collaborative Editing[END_REF], based on the same principles as operational transformation, but sacrificing the breadth of the supported content types to gain simplicity. WOOT algorithm does not require central servers nor vector clocks, and uses a simple algorithm for merging operations. However, it only applies to linear text structures and supports a reduced set of operations: insert and delete. Basically, the algorithm works 1 as follows.

WOOT sees a document as a sequence of blocks, or elements, where a block is a unit of the text, with a given granularity: either a character, word, sentence, line or paragraph. Once created, a block is enhanced with information concerning unique identification and precise placement even in a highly dynamic collaborative environment, thus becoming a W-character. Formally, a W-character is a fivetuple < id, α, v, id cp , id cn >, where:

• id is the identifier of the W-character, a pair (ns, ng), consisting of the unique ID of the peer where the block was created, and a logical timestamp local to that peer;

• α is the alphabetical value of the block;

• v indicates whether the block is visible or not;

• id cp is the identifier of the previous W-character, after which this block is inserted;

• id cn is the identifier of the following W-character.

1 For a more detailed description, please refer to [START_REF] Oster | Data Consistency for P2P Collaborative Editing[END_REF] When a block is deleted, the corresponding W-character is not deleted, but its visibility flag is set to f alse. This allows future blocks to be correctly inserted in the right place on a remote site, even if the preceding or following blocks have been deleted by a concurrent edit. W-characters corresponding to the same document form a partially ordered graph, a W-string, which is the model on which WOOT operates. Every user action is transformed into a series of WOOT operations, which include references to the affected context (either predecessor and successor elements, either the element to be removed), then exchanged between peers. An operation always affects exactly one element: a block can be added to, or removed from the content. Upon receiving a remote operation, it is added to a queue and will be applied when it is causally ready, meaning that the preceding and following W-characters are part of the W-string in case of an insert operation, or the target W-character is part of the W-string in case of a delete operation.

When a document must be displayed, the WOOT algorithm computes a linearization of the W-string, and only the visible block are returned. This linearization is computed in such a way that the order of reception of the operations does not influence the result, as long as all the operations have been received.

The UniWiki Architecture

The central idea of our paper is to use a DHT system as the storage mechanism, with updates handled by running WOOT algorithm directly in the DHT nodes. This integration is possible by changing the behavior of the put and get methods. Instead of storing the actual wiki document as plain text content, each DHT node stores the corresponding W-String. On display, the DHT reconstructs a simplified version of the document, which is further processed by a wiki server front-end. On update, the wiki front-end creates a list of changes made by the user, which are transformed into WOOT operations that are applied inside the DHT.

Since a continuous synchronization is needed between all sites in a total replicated system, it is practical to restrict their number, as it is done, for instance, in the current architecture of Wikipedia. However, as the DHT allow accesses from many clients at the same time, in our approach wiki front-ends can be placed in numerous sites, without the need for any synchronization between them. Front-ends can be added or removed at any moment, because the entire data is stored outside the front-end, in the DHT. Also, the specifics of DHT systems allow adding and removing peers from the DHT even at high rates, thus opening the storage system for third-party contributions.

Overview

Basically, our system consists of two parts, as depicted in Figure 1: the DHT network, responsible for data storage, and the wiki front-ends, responsible for handling client requests. The DHT storage network is a hybrid network of dedicated servers and commodity systems donated by users, responsible for hosting all the data inside the wiki in a peer to peer manner. As in any DHT, each peer is assigned responsibility for a chunk of the key space to which resources are mapped. In our context, each peer is therefore responsible for a part of the wiki content. The information is stored on a peer in the form of a WOOT model. This allows to tolerate concurrent updates, occurring either when parallel editions arise from different access points, or when temporary partitions of the network are merged back. The WOOT algorithm ensures eventual consistency -convergence -on the replicated content stored by peers responsible for the same keys.

DHT storage

DHT node wiki frontend clients clients

The wiki front-ends are responsible for handling client requests, by retrieving the WOOT pages for the requested page from the DHT, reconstructing the wiki content, rendering it into HTML, and finally returning the result to the client. In case of an update request, the front-end computes the textual differences corresponding to the changes performed by the user, transformes them into WOOT operations, then sends them to the DHT to be integrated, stored and propagated to the replicated peers.

Data model

As explained in section 2.2 and in [START_REF] Oster | Data Consistency for P2P Collaborative Editing[END_REF], WOOT works not with the plain textual content of a document, but with an enriched version of it, in the form of a W-string. This is the WOOT page model that is stored inside the DHT, at each peer responsible for that document.

To update this model, WOOT operations computed from the user's changes are inserted in the DHT, first by calls to the put method, and then by inherent DHT synchronization algorithms.

Determining the actual changes performed by the user requires not just the new version of the content, but also the original version on which he started editing. And, since transforming textual changes into WOOT operations requires knowing the WOOT identifiers corresponding to each block of text, this means that the front-end must remember, for each user and for each edited document, the model that generated the content sent to the user. However, not all the information in the complete WOOT page model is needed, but just the visible part of the linearized W-string, and only the id and actual block content. This simplified W-string -or, from a different point of view, enriched content -is called the WOOT page, and is the information that is returned by the DHT and stored in the front-end.

When sending the page to the client, the front-end further strips all the meta-information, since the client needs only the visible text. This is the plain wiki content which can be transformed into HTML markup, or sent as editable content back to the client.

Algorithms

This section describes in term of algorithms the behaviors of a front-end server and of a DHT peer.

Behavior of a Front-end Server

The behavior of a front server can be summarized as follows. When a client wants to look at a specific wiki page, the method onDisplay() is triggered on the front-end server. First, the server retrieves the corresponding WOOT page from the DHT, using the hashed URI of the requested wiki content as the key. The received WOOT page is transformed into plain wiki content, which is rendered as HTML if necessary, then sent to the client.

onDisplay(contentURI)

wootPage = dht.get(getHash(contentURI)) wikiContent = extractContent(wootPage) htmlContent = renderHTML(wikiContent) return htmlContent When a client requests a particular page in order to edit it, the method onEdit() is called on the front-end server. The WOOT page retrieved from the DHT is stored in the current editing session, so that the changes performed by the user can be properly detected (the intention of the user is reflected on the initial content displayed to him, and not on the most recent version, which might have changed). Then the wiki content is sent to the client for editing.

onEdit(contentURI)

wootPage = dht.get(getHash(contentURI)) session . store(contentURI, wootPage) wikiContent = extractContent(wootPage) return wikiContent When a client terminates his editing session and decides to save his modifications, the method on-Save() is executed on the front-end server. First, the old version of the wiki content is extracted from the current editing session. A classical textual differences algorithm [START_REF] Myers | An O(ND) Difference Algorithm and its Variations[END_REF] is used to compute modifications between this old version and the new version submitted by the client. These modifications are then mapped2 on the old version of the WOOT page in order to generate WOOT operations. Finally, these WOOT operations are submitted to the DHT.

Behavior of a DHT Peer

In order to comply to our architecture, the basic methods generally provided by a DTH peer have to be updated. Their behaviors differ from the basic behaviors provided by any DHT since the type of the value returned by a get request -a WOOT page -is not the same as the type of the value -a list of WOOT operations -stored by a put request. When a get request is received by a DHT peer (which means that it is responsible for the wiki content identified by the targeted key), the method onGet() is executed. The WOOT page model corresponding to the key is retrieved from the local storage, the simplified WOOT page is extracted, and then sent back to the requester -generally, a front-end server.

onGet(key)

wootPageModel = wootStore.get(key) wootPage = extractVisiblePage(wootPageModel) return wootPage

When a DHT peer has to answer to a put request, the method onPut() is triggered. First, the targeted WOOT page model is retrieved from the local storage. Then, each operation received within the request is integrated in the actual WOOT page and logged in the history of that page.

onPut(key, wootOps[])

wootPageModel = wootStore.get(key) for (op in wootOps[]) integrate (op, wootPageModel) wootPageModel.log(op)

Generally, DHTs provide a mechanism for recovering from abnormal situations such as transient or permanent failure of a peer, message drop on network, or simply new nodes joining. In such situations, after the execution of the standard mechanism that re-attribute the keys responsibility to peers, the method onRecover() is called for each key the peer is responsible for.

The goal of the onRecover() method is to reconciliate the history of a specific wiki content with the current histories of that content stored at other peers responsible for the same key. By the usage of the WOOT integration algorithm, reconciliating histories will also ensure convergence on the replicated WOOT models.

The method starts by retrieving the targeted WOOT page model and its history. Then, a digest of all the operations contained in this history is computed. Further, the method antiEntropy() is called on another replica -another peer responsible for the same key -in order to retrieve operations that the peer could have missed. Finally, each missing operation is integrated in the WOOT model and is added to its history.

Implementation

Over the last few years, many DHT implementations have been released. These systems take advantage of the computing at the edge paradigm, where resources available from any computer in the network can be used and are normally made available. However, contrasting with the client-server model, where few powerful servers provide all the computing and storage power to a much larger network of clients. Nevertheless, such decentralized architectures also introduce new issues which have to be taken care of. Some of these issues include how to deal with constant node joins and leaves, network heterogeneity, and many others. Also, another important issue is the development complexity of new applications on top of this kind of networks. For these reasons, we need a middleware platform that provides the necessary abstractions and mechanisms to construct distributed applications.

Following the ideas developed in previous sections, we want to implement our algorithms over a DHT system. In this line, we summarize the objectives of our implementation in three points:

• Modify the put and get DHT methods behavior.

• Establish replication strategies and handle replicas.

• Add consistency logic in these DHT mechanisms.

In this setting, another important aspect is that we want to change the behavior of the DHT system. To address this problem, there are different options, but it is clearly a good scenario to apply distributed interception mechanisms.

The benefits of this approach will be:

• Full control of the DHT mechanisms, including runtime adaptations.

• Decoupled architecture between wiki front-end and DHT sides.

• Legacy and transparency for wiki front-end applications.

Lastly, we propose the use of a distributed P2P interception middleware, called Damon [START_REF] Mondéjar | Building a distributed AOP middleware for large scale systems[END_REF], that fulfills the DHT, middleware, and interception requirements.

Damon Overview

By making efficient use of DHT substrates and dynamic interception mechanisms, Damon is designed as a fully distributed interception middleware. Its main goal is to provide the necessary abstractions and services to develop distributed P2P interceptors. A description of them is shown as follows. However, for more detailed information on Damon, please see [START_REF] Mondéjar | Damon: a decentralized aspect middleware built on top of a peer-to-peer overlay network[END_REF][START_REF] Mondéjar | Building a distributed AOP middleware for large scale systems[END_REF] Mainly, Damon provides new features (i.e. scalability) to existent or new applications transparently. Therefore, distributed interception presents a different philosophy than traditional distributed solutions like remote object or component models. Usually, when one designs a new application, he creates the main aspect without any distributed concern in mind. Simply, we may design the main concern first by thinking in local, and later implementing the rest of the distributed interception application designing the necessary concerns (i.e. distribution).

The main features of Damon are:

• P2P Routing: taking advantage of the built-in DHT-based P2P network, Damon allows key-based, direct-node and neighbor routing abstractions.

• Distributed Composition Model: this model allows connection-oriented features. In addition, the composition model allow us to make a good abstraction, clear interaction scheme, and reconfiguration in runtime.

• Distributed Interception: this mechanism was introduced to allow source hooks for local interception, and remote calls for distributed purposes. Another important feature, is which Damon supports interception of their own remote connectors. This own interception can be performed before, during, and after the call routing.

Following these ideas, developers can implement and compose distributed interceptors in large-scale environments. When the local interception (source hook) is peformed, these distributed interceptors trigger the remote calls via P2P routing abstractions.

UniWiki Implementation

Like traditional wiki application (i.e. Wikipedia), we have the local execution of our wiki front-end. This scenario is ideal to apply distributed interception, because we can intercept the local behavior to extend/compose the necessary concerns. Thereby, using Damon we are able to inject our algorithms of distribution, replication, and consistency transparently.

In Figure 2 we can see the UniWiki source hook, where we aim to intercept locally the typical wiki methods of store and retrieve (in this case we use a generic example), in order to distribute remotely. In addition, the source hook solution helps to separate local interception, interceptor code, and the wiki interface. On the other hand, source hooks have other benefits like a major level of abstraction, or degree of accessibility for distributed interceptors.

Interception Points <<Source Hook>>

Wiki Interface Locator +! save (url, page) +! load (url) : page wikiapp.Operations +! store (id, page) +! retrieve (id) : page +! around : store (joinpoint, id, page) +! around : retrieve (joinpoint, id)

Interception Framework Wiki Application

UniWiki Implementation Following such approach, integration with other wiki applications is quite simple, and can be easily used for third party wiki applications, including different versions, transparently.

Replication Consistency

Integrator Replicator We now describe the UniWiki execution step by step as shown in Figure 3, focusing on the integration of the algorithms and the interaction of the different concerns. In this line, we analyze the context, and extract three main concerns that we need to implement: distribution, replication and consistency.

Obviously, distribution is the main concern, and in our solution uses the key-based routing abstraction. The replication concern is also based on P2P mechanisms, and follows the neighbors strategy. Finally, as we see in previous section, the consistency concern remains on the WOOT algorithm. In this implementation, it allows edition, patching, and merging of wiki pages, and it performs these operations via distribution calls interception. 1. The starting point of this application is the wiki interface used by the existing wiki application. We therefore introduce the Wiki Interface source hook that intercepts the save, and load methods. Afterward, the Locator distributed interceptor is deployed and activated on all nodes of the UniWiki network. Its main objective is to locate the responsible node of the local insertions and requests.

Distribution:

2. These save executions are propagated using the put connector. Consequently, the remote calls are routed to the key owner node, by using their url to generate the key through the key-base routing.

3. Once the key has reached its destination, the registered connectors are triggered on the Storage instance running on the owner host. This distributed interceptor has already been activated on start-up on all nodes. For request case (get), the idea is basically the same, with the Storage receiving the remote calls.

4. Furthermore, it propagates later an asynchronous response using the return call via direct node routing. Finally, the get values are returned to the Locator originator instance, using their own connector.

Once we have the wiki page distribution running, we may add new functionalities as well. In this sense, we introduce new distributed interceptors in order to extend or modify the current application behavior in runtime. More specifically, these instances add new important services (replication and consistency) as shown right away.

Replication:

1. When dealing with the save method case, we need to avoid any data storage problems which may be present in such dynamic environments as large-scale networks. Thus, data is not only to be stored on the owner node, because if this host leaves the network for any reason, its data would surely become unavailable. In order to address this problem, we activate the Replicator interceptor in runtime, which following a specific policy. The Replicator has a connector called onPut, which intercepts the Storage put requests from the Locator service in a transparent way.

2. Thus, when a wiki page insertion arrives to the Storage instance, this information is re-sent (replicate) to the ReplicaStore instances activated in the closest neighbors. 3. Last but not least, ReplicaStore distributed interceptors are continuously observing the state of the copies that they are keeping. If one of them detects that the original copy is not reachable, it re-inserts the object again, using a remote connector put, in order to replace the Locator remote call.

Consistency: Based on the WOOT framework, we create the Editor (situated on the front-end side) and the Integrator (situated on the back-end side) distributed interceptor, those intercept the DHT-based calls to perform the consistency behavior. Their task is the modification of the distribution behavior, adding the patch transformation in the edition phase, and the patch merging in the storage phase.

1. The Editor distributed interceptor owns a connector (edit) that intercepts the return remote calls from Storage to Locator instances. This mechanism stores the original value in a session. Obviously, in a parallel way, the Integrator prepares the received information to be rendered as a wiki page.

2. Later, if the page is modified, a save method triggers the put mechanism, where another connector (patch) transforms the wiki page into the patch information by using the saved session value.

3. In the back-side, the Integrator instance intercepts the put request, and merges the new patch information with the back-end contained information. The process is similar to the original behavior, but changing the wiki page with a consistent patch information.

4. In this setting, having multiple replicated copies, leads to inconsistencies. We use the antiEntropy technique, in order to recover a log of differences among each page and their respective replicas. Finally, the Integrator sends the necessary patches to be sure that all copies remain consistent.

• Description: In this experiment we introduce problems on a specific fraction of the network. In this case, each host inserts 1000 wiki pages, and retrieves 1000 on them randomly. The objective of this test is to check persistence and reliable properties of our system. After the insertions, a fraction of the hosts fail without warning, and we try to restore these wiki pages from a random existing host.

• Results: We can see the excellent results in Figure 5. Even in the worst case (50% of network fails at the same time), we have a high probability (average of 99%) to activate the previously inserted wiki pages.

• Why: The theoretical probability that all the replicas for a given document fail is n i=1 r i = r 1 * r 2 * ... * r n = (r) n where n is the replication factor and r the probability that a replica fails. For instance, when r = 0.5, and n = 6, the result is (0.5) 6 ≈ 0.015 ≈ 1.5%.

Finally, for consistency we study the performance of our operations.

• Objective: demonstrate that our routing abstraction is efficient in terms of time and network hops.

• Description: similar to the previous experiment, we create a 120 hosts network, and each host inserts and retrieves 1000 times the same wiki page. The idea is that the initial value is modified, and retrieved concurrently. In this point, we make this experiment twice. The first time with consistency mechanisms disabled (only the put call), and the second time with these mechanisms enabled (patch and merge). In the last step, the consistency of the wiki page is evaluated for each host.

• Results: for this experiment, we found that the consistency is guaranteed by our system. We can see the operation times in Figure 5, and for each operation the number of hops has an average of 2. Therefore, the wiki page put operation has an average time of 145 ms, and an overall overhead of: 3.45. For update operations the value is logically higher : 164 ms. with an overhead of 3.90. Finally, the update operation overhead respects put operation, when the consistency operation is performed, is 1.13.

• Why: Due to the nature of the Grid experimentation platform, latencies are low. Moreover, we consider that the operation overhead is also low. Finally, theoretical number of hops is logarithmic respect the size of the network. In this case, log (120 hosts) = 2 hops.

Conclusions and Future Work

In this paper we propose an efficient P2P system for storing distributed wikis, extended to large-scale scenarios transparently. In this line we present the algorithms, a prototype, and the experimentation. Nowadays, many solutions for wiki distribution are proposed, but as we can see in the Section 2.1, the current approaches focus on only one half of the problems, failing to address both efficient distribution and correct replication. We combine two intensively studied technologies, each one addressing a specific aspect: distributed hash tables are used as the underlying storage and distribution mechanism, and WOOT ensures that concurrent changes are correctly propagated and merged for every replica.

We propose a completely decoupled architecture, where our solution is totally abstracted from the real wiki application. In our approach we define the storage behavior from the scratch, apply this behavior on an existing DHT library, and the wiki presentation and business logic is full provided by the wiki application. Therefore, for our implementation we use a distributed interception middleware over DHTbased networks, called Damon.

Validation of UniWiki has been conducted on the Grid'5000 testbed. We have proved that our solution is viable in large-scale scenarios, and that the system has acceptable performance. Our experiments where conducted with real data [START_REF]Wikipedia Data[END_REF] from Wikipedia which include almost 6 million entries.

Finally, UniWiki can be downloaded at http://uniwiki.sourceforge.net/, under a LGPL license.

In the near future, we plan to apply our approach to a more sophisticated front-end, the XWiki application server. Other future directions include studying how to manage security access on wiki applications deployed on our proposed peer-to-peer network, and how to perform search.

Figure 1 :

 1 Figure 1: UniWiki architecture overview.

  onSave(contentURI, newWikiContent) oldWootPage = session.get(contentURI) oldWikiContent = extractContent(oldWootPage) changes[] = diff (oldWikiContent, newWikiContent) wootOps[] = ops2WootOps(changes[], oldWootPage) dht.put(getHash(contentURI), wootOps[])

Figure 2 :

 2 Figure 2: Wiki Source Hook Interface.

Figure 3 :

 3 Figure 3: UniWiki composition diagram.

Figure 4 :

 4 Figure 4: Empirical results -Distribution.

Figure 5 :

 5 Figure 5: Empirical results -Replication.

Figure 6 :

 6 Figure 6: Empirical results -Consistency.

  Existing Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 The UniWiki Architecture 3.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Data model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Behavior of a Front-end Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.3.2 Behavior of a DHT Peer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Damon Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 UniWiki Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

	Contents
	1 Introduction
	2 Related Work
	2.1 4 Implementation
	4.1 6 Conclusions and Future Work
	7 Acknowledgments

5 UniWiki Evaluation 5.1 Testbed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

RR n°6848

A thorough description of the mapping algorithm is provided in[START_REF] Weiss | Wooki: a P2P Wiki-based Collaborative Writing Tool[END_REF].RR n°6848

Acknowledgments

Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, an initiative from the French Ministry of Research through the ACI GRID incentive action, INRIA, CNRS and RENATER and other contributing partners (see https://www.grid5000.fr/). This work has been partially funded by the Spanish Ministry of Science and Technology through project P2PGRID TIN2007-68050-C03-03.

UniWiki Evaluation

We have conducted several experiments to measure the viability of our UniWiki system. We have used Grid'5000 [START_REF] Bolze | Grid'5000: A Large Scale and Highly Reconfigurable Experimental Grid Testbed[END_REF]. The Grid'5000 platform is a large-scale distributed environment that can be easily controlled, reconfigured and monitored. The platform is built with 5000 CPUs distributed over 9 sites in France. Every site hosts a cluster and all sites are connected by a high speed network.

In this sense, we conducted the experiments using 120 real nodes from the Grid'5000 network, located in different geographical locations, including Nancy, Rennes, Orsay, Toulouse, and Lille.

Finally, for our prototype we chose the DHT Implementation of Pastry (FreePastry) for its efficient Java implementation. In addition, for local interception we use an Aspect-Oriented Programming (AOP) [START_REF]Aspect-Oriented Software Development Community[END_REF] framework.

Testbed

When analyzing our large-scale system we have three main concerns: load-balancing in data dispersion among all nodes (distribution), failed hosts that do not affect system behavior (replication), and the operation performance (consistency).

For distribution, we study the data dispersion in the network.

• Objective: demonstrate that when our system works with a high number of hosts, is able to store a real large data set of wiki pages, and that all the information is uniformly distributed among them.

• Description: create a network of 120 hosts, and using a recent Wikipedia snapshot, we introduce their 5,688,666 entries. The idea is that data distribution is uniform, and each host has a similar quantity of values (wiki pages).

• Results: we can see in Figures 4 that we have a system working and the results are as expected.

Thereby, the distribution of data trends to be uniform. Results indicate that each host has an average of 47,406 stored wiki pages, and using an approximate average of space (4.24 KB) per wiki pages we have 196 MB, with a maximum of 570.5 MB (137,776 values) in one node.

• Why: Uniform distribution of data is guaranteed by the key-based routing substrate, and by the hash function (SHA-1) employed to generate the keys. However, with this number of hosts (120) the distribution values show that a 54.17% are over the average, and a 37.5% are over the double of the average. Furthemore, we can see similar results in simulations (using PlanetSim [START_REF] Planetsim | [END_REF]), with a random distribution of 120 nodes.

We make another simulation with 1000 nodes using the same DHT simulator. The results of this last simulation (Figure 7) shows that the values are: 63.7% over average and 20.6% over double of the average, because with a high number of nodes the uniformity is improved. Secondly, we study the fault-tolerance of our system platform.

• Objective: demonstrate that in a real network with failures, our system continues working as expected.


Sajeeva Abeywardena

Eisa Anwar

Stuart Miller

Ildar Farkhatdinov

Human balance augmentation via a supernumerary robotic tail

Humans are intrinsically unstable in quiet stance from a rigid body system viewpoint; however, they maintain balance thanks to muscular and neuro-sensory properties whilst still exhibiting postural sway characteristics. This work introduces a one-degree-of-freedom supernumerary tail for balance augmentation in the sagittal plane to negate anteriorposterior postural sway. Simulations showed that the tail could successfully balance a human with impaired ankle stiffness and neural control. Insights into tail design and control were made; namely, to minimise muscular load the tail must have a significant component in the direction of the muscle load, mounting location of the tail is significant in maximising inertial properties for balance augmentation and that adaptive control will exploit augmentation characteristic of the tail best for different loads held by a wearer.

I. INTRODUCTION

Quiet standing analysis has shown that it is valid to model a human in an upright pose as an inherently unstable inverted pendulum [START_REF] Winter | Stiffness control of balance in quiet standing[END_REF]- [START_REF] Morasso | Quiet standing: The single inverted pendulum model is not so bad after all[END_REF]. Due to the musculoskeletal and sensorimotor systems, the toppling torque induced by the gravitational force is negated and humans maintain upright balance so long as their centre of mass (CoM) is within the base of support (BoS). Nevertheless, due to the instability of the natural dynamical system, humans exhibit postural sway whilst in a quiet stance. Coupled with factors such as muscle fatigue, neurological disorders, and loss of vestibular function; the CoM can momentarily shift outside the BoS which is enough to cause the dynamics to become unstable and the human losing balance as a result.

Research has been conducted to augment human balance with robotic assistance. Exoskeletons are directly attached to a wearers natural limbs (NLs), and are used to augment their force capabilities at a joint level. A recent study showed that back support exoskeletons reduced postural sway in quiet stance [START_REF] Park | Effects of two passive back-support exoskeletons on postural balance during quiet stance and functional limits of stability[END_REF]; whilst other strategies have included applying an assistive torque at the pelvis to provide balance support during gait and the implementation of a stepping strategy for balance recovery [START_REF] Monaco | An ecologicallycontrolled exoskeleton can improve balance recovery after slippage[END_REF], [START_REF] Farkhatdinov | Assisting human balance in standing with a robotic exoskeleton[END_REF]. Due to being attached in parallel with the NLs of the wearer; exoskeletons share the same kinematic properties as the assisted limb but the added mass and footprint of the wearable device can hinder the natural motion capabilities of the limbs.

Gyroscopic systems and robotic tails mounted posterior to the trunk have been used to provide human balance assistance with independent kinematic workspaces to the NLs. In gyroscopic systems, the principal of precession is utilised to counteract the torque caused by postural sway [START_REF] Romtrairat | An application of scissored-pair control moment gyroscopes in a design of wearable balance assistance device for the elderly[END_REF], [START_REF] Lemus | Controller synthesis and clinical exploration of wearable gyroscopic actuators to support human balance[END_REF]. Whilst these systems provide balance, they come at the cost of significant added mass of 10-16 kg with an extra 10 kg shown to be detrimental to the motion of human NLs [START_REF] Meuleman | The effect of directional inertias added to pelvis and ankle on gait[END_REF]. Taking inspiration from animals, robotic tails utilise swinging inertia for balance augmentation [START_REF] Nabeshima | Arque: Artificial biomimicry-inspired tail for extending innate body functions[END_REF], [START_REF] Maekawa | Dynamic assistance for human balancing with inertia of a wearable robotic appendage[END_REF]. In these systems, the swinging mass ranged between 1.6-2 kg; however, this was achieved via a ground mounted air compressor [START_REF] Nabeshima | Arque: Artificial biomimicry-inspired tail for extending innate body functions[END_REF] or a total added system mass of 9 kg [START_REF] Maekawa | Dynamic assistance for human balancing with inertia of a wearable robotic appendage[END_REF]. Further, the one-degree-of-freedom (dof) tail in [START_REF] Maekawa | Dynamic assistance for human balancing with inertia of a wearable robotic appendage[END_REF] was designed to counteract external perturbations in the coronal plane; therefore, the swinging inertia will not negate anteriorposterior (AP) postural sway induced by gravity.

The previous work in supernumerary tails have shown ability to provide balance for a human; however, a systematic control framework was not utilised. In this work, we propose a one-dof robotic tail for quiet standing balance in the sagittal plane and use state space control for methodical control development. The dynamics of the system is modelled in Section II, a simulation study to examine the effectiveness of the tail to augment balance and impact on muscular load in dorsiflexion conducted in Section III, and the consequences of the presented framework for informed design of robotic assistance discussed in Section IV.

II. SYSTEM MODELLING AND CONTROL

The traditional model of quiet standing models the human with hands by the side as one rigid body, with one-dof at the ankle joint that acts in the sagittal plane and the CoM of the human located in the axis which gravity acts but in opposing direction. Hence, the torque due to gravitational force in this pose is null and the human will remain balanced unless perturbed by an external disturbance. In many quiet standing scenarios, the arms are conducting a task in front of the torso or holding a load. As such, the CoM of the system (human and load) m s is displaced slightly forward, particularly as load m l increases. The gravitational torque is no longer null and can lead to instability. Hence, suitable control action is required by the human to maintain the CoM within the BoS. Depending on scenario, increased muscle fatigue and mental tiredness inducing longer neuromechanical delay of the neural control element while negatively impact the ability to maintain upright posture. It is hypothesised that a tail can assist in compensating for the unstable dynamics in the quiet standing model. As these instabilities are induced by a torque created by rotational motion, a simple concept to counteract that is by utilising a one-dof tail that swings in an arc in the sagittal plane as illustrated in Fig. 1.

x 0 y 0 BoS m s x 1 y 1 x 2 y 2 m a m l m t m b l l l t l a w a h h t h b h a h l w w l d l µ 1 µ 2 f t f m f t,m g = 9.81 m/s
Fig. 1: Conceptual swinging arc tail with frame assignment and geometric parameters

A. Geometric and Inertial Parameters

Due to the assumption that the human can be modelled as an inverted pendulum in an upright pose, it is suffice to consider the body m b (legs, trunk, head), forearm m a and load m l as one rigid body. Hence, the CoM m s of the composite rigid body (CRB) system can be found. This rigid body has one-dof, i.e. the rotation of the ankle about F 0 by θ 1 . The conceptual tail is modelled as a separate body mounted to the human at a distance h t along the x 1 axis and which swings in an arc through an angle of θ 2 about z 2 .

B. Inverse Dynamic Model

The inverse dynamic model (IDM) correlates the generalised forces to the motion states of the joints via an inertial mapping. It can be utilised to calculate the required joint torques to follow a prescribed motion trajectory of an inertial rigid body that could be subjected to external forces. In general, utilising an appropriate method such as Newton-Euler (NE), Euler-Lagrange (EL) or Natural Orthogonal Complement (NOC) [START_REF] Angeles | Fundamentals of Robotic Mechanical Systems: Theory, Methods and Algorithms[END_REF], [START_REF] Abeywardena | Inverse dynamic modelling of a threelegged six-degree-of-freedom parallel mechanism[END_REF], the IDM can be written as

Su + u p = M (q) q + C (q, q) q + G (q) (1)
where q are the generalised joint coordinates, M is the n × n generalised inertia matrix, C is an n × n matrix related to the centripetal and Coriolis torques, G the vector of generalised gravity forces, u are generalised active forces, u p are generalised passive forces (i.e. joint stiffness) and S is an n × n diagonal matrix that selects whether the joint is an active (1) or passive (0) input.

C. Linearised State Model

Equation ( 1) is of use when the trajectory of the generalised co-ordinates is known a-priori and the associated generalised forces are required. However, in many situations, it is of more use to analyse the behaviour of the dynamical system from the perspective of the motion variables, i.e human balance. This is known as the forward dynamic model (FDM), i.e. the dual model to the IDM whereby

q = -M -1 (C q + G) + M -1 (Su + u p ) (2)
From Eq. ( 2), it is evident that the generalised inertia matrix is critical in the open loop response of the system, and how a control input is transformed to impact the system response. This is a set of non-linear second-order ordinary differential equations (ODEs) which can be transformed into a system of first order ODEs by defining the state vector x = q T , qT T . Due to the non-linearity that encompasses the workspace of the system, control input design can be complex. However, if only a sub-workspace is of operational interest, the dynamics can be linearised about a stationary point (x, ū); allowing for concepts of linear time invariant systems to be applied. This is the case for human balance where the operational point of interest is the upright posture. As such, the linearised dynamics about the stationary point can be expressed as the system of first order linear ODEs,

ẋ = Ax + Bu (3)
where A and B are the linearised state and input matrices.

For the swinging arc tail proposed, the state vector is

defined as x = θ 1 , θ 2 , θ1 , θ2
Thus, the stationary point about which the system is linearised is dependent on the mass of the load being held. Further, from Eq. ( 4), a constraint exist on the properties of tail length and mass (hence, inertial capabilities) such that the system can be statically balanced, i.e. m t l t ≥ m a l a + m l l l .

D. Control Inputs

With the model of the system defined, an understanding of the control inputs is required. The selection matrix which dictates if the modelled joint is active or passive is S = diag ([0, 1]) as the first row of Eq. ( 1) correspond to the torque of the ankle and the second to the tail torque. It was initially proposed that humans maintain upright posture due solely to a stiffness control model employed by the ankle [START_REF] Winter | Stiffness control of balance in quiet standing[END_REF]; however, it was shown that the stiffness required exceeded physiological values and hence a neural control element assists in providing balance [START_REF] Morasso | Can muscle stiffness alone stabilize upright standing?[END_REF], [START_REF] Peterka | Postural control model interpretation of stabilogram diffusion analysis[END_REF]. These properties can be modelled as passive inputs u p in terms of the states of the ankle [START_REF] Peterka | Postural control model interpretation of stabilogram diffusion analysis[END_REF], [START_REF] Morasso | Quiet standing: The single inverted pendulum model is not so bad after all[END_REF] , i.e.

u p = u ank + u nm u ank = κ p θ1 -θ 1 + κ d θ1 -θ1 u nm = k p θ1 -θ 1 (t -τ d ) + k d θ1 -θ1 (t -τ d ) (5)
where u ank is an impedance model of the ankle joint and u nm is the neural control input represented by a proportional-derivative control with time delay τ d . The time delay changes the state equation governed by Eq. (3) from a system of first order ODEs into a delay differential equation (DDE). As a consequence, the characteristic equation of the system is now a quasi-polynomial which has infinite poles (eigenvalues), complicating control design. However, as τ d → ∞, the delay becomes insignificant in terms of control. For human balance, this is symbolic of increasing strain on the neuro-controller due to mental tiredness, inherent motor control disorders or loss of vestibular function, i.e. situations where the tail is of increased value to circumvent loss of balance. Including the passive control element u ank , assumes that the ankle will be able to provide a consistent level of compensatory torque and does not factor in muscle fatigue. As such, any ability of the tail to reduce muscular fatigue is void by including this term. Hence, to investigate the potential of a tail to augment human balance whilst reducing muscular load, the worst case scenario of large neuromechanical delay and no resistive ankle torque is considered, i.e. u p = 0. As such, there is only one input to the system, the torque of the tail represented by u.

E. Force Analysis

A hypothesis of the tail is that muscular load in quiet standing for able-bodied users will be reduced. A force analysis can be conducted to investigate this assertion. The compensatory torque to AP sway of the ankle is created by the plantar and dorsiflexors. When the CoM exceeds the BoS, the ankle must dorsi-flex to oppose gravity. To investigate the impact the tail has on muscle force, the overall tail force can be projected into a component that acts in the direction of the dorsiflexors when θ1 < 0. A line model of the dorsiflexor is used, where it attaches half way from the forefoot up to the top of tibia (0.5 m [START_REF]Anthropometry and biomechanics[END_REF]) as illustrated in Fig. 1. For this analysis, κ p = 494 Nm/rad and κ d = 30 Nm-s/rad [START_REF] Morasso | Quiet standing: The single inverted pendulum model is not so bad after all[END_REF].

III. SIMULATION

A simulation of the human-tail system in Fig. 1 was conducted, with and without a 5 kg load held.

A. Parameters

The geometric and mass parameters 1 related to Fig. 1 are tabulated in Table I where the anthropometric parameters are derived from [START_REF]Anthropometry and biomechanics[END_REF]. The length of the tail was fixed at 0.9 m, in line with [START_REF] Maekawa | Dynamic assistance for human balancing with inertia of a wearable robotic appendage[END_REF] and a swinging mass of 5 kg selected. Note, in [START_REF] Maekawa | Dynamic assistance for human balancing with inertia of a wearable robotic appendage[END_REF], the human was 22 kg less than here and the ability to maintain balance was assumed in control. The tail was simulated at two heights, the CoM of the body i.e. h b and 20 cm above at 1.2 m (around mid back) to ensure ground clearance and investigate the effect of added inertia. The inertia of the human in the sagittal plane was 12.9 kg-m 2 [START_REF]Anthropometry and biomechanics[END_REF]. The BoS was defined as a foot of 0.25 m with a rearfoot to forefoot ratio of 0.08:0.17 [START_REF] Suga | Calcaneus height is a key morphological factor of sprint performance in sprinters[END_REF]. As such, the CoM exceeds the BoS when θ 1 = 9.5 • . Full state feedback control laws of u = -Kx were developed, with the effect of non-dominant 1 Note, for the arm, la is reported as half the total length of the segments and the mass corresponds to two arms.

B. Results and Discussion

The human-tail system was simulated with an initial condition of x 0 = [8 • , 0, 0, 0], i.e. when the CoM is about to exceed the BoS. In a physical realisation, the controller would aim to prevent the human from reaching this posture. Figures 2 and3 show the results of the simulation at the two mounting height levels. From the simulation it is evident that the proposed tail can provide balance with and without load. The tail being higher allowed for more clearance from the body due to the extra inertia, with lower θ 2 values. Further, the trajectory of the tail is lower magnitude and settles quicker with η = 10, i.e. when the non-dominant poles are further away. The caveat to this is that greater torque is required which can impact the amount of force required from the antagonistic muscle in the case of an able human. Further, more damping was used to balance the system with no load (0.75) compared to load (0.6), indicating that an adaptive control methodology would be required for a fully encompassing system that considers multiple load cases. It was hypothesised that muscle force could be reduced with the tail. However, due to its rotational nature, reduction in muscle force will only be apparent when the tail force has a significant component in the direction of the muscle. This result is critical, as it is useful for informed design of a tail; suggesting that a one-dof revolving tail is not the most optimal solution if reducing muscle force is the key criteria. Nevertheless, this simulation considered the worst case scenario of no ankle stiffness control and severely impaired neural control. As such, these results proved the validity and provide an upper bound on the requirements for a one-dof revolute tail to negate AP sway in the sagittal plane, i.e. for a tiring warehouse worker holding load, the tail will be beneficial to maintain upright posture as fatigue sets in and AP sway becomes apparent. For a physical realisation of the tail, the required motion and torque will be reduced due to the musculoskeletal and sensorimotor system providing extra resistive torque. Hence, the mass and length of the tail that dictate the inertial properties to create the coumpensating torque can be reduced based on the level of assistance required for the potential tail application, i.e. reduction in muscle loads for physically able versus full balance augmentation of those with motor impairment.

IV. FUTURE WORK

It was shown that a simple one-dof revolute tail is able to provide human balance augmentation of AP sway in the sagittal plane. A key outcome of this work is the systematic approach to the control which can lead to informed design of robotic tails. This study and previous work of other authors show the importance in maximising the inertia of the tail to provide a counteracting torque. However, increasing mass and length have consequences, i.e. added strain on the body and workspace implications. Potential future avenues with this in consideration are to select an application of the tail to determine the level assistance required; include the delay dynamics of neural control which provide added stabilisation to the system and hence reduce the level of assistance required from the tail; and to investigate tails with added dofs which could add inertia to the system with a wider workspace and allowing for two control goals, i.e stabilisation and muscle load. Hence, this work has shown critical considerations for the field of physical human-robot interaction where logical simulation can lead to design which successfully achieve the desired task while minimising impact on a human.

T

  and is linearised about the upright stance posture x1 = θ1 = 0. The stationary value of the tail, x2 = θ2 is the angle which statically balances the system in upright pose. With reference to Fig.1, summing torques due to gravity around the ankle joint yields θ2 = arcsin m a l a + m l l l m t l t

Fig. 2 :

 2 Fig. 2: Simulation with the tail mounted at the CoM

Fig. 3 :

 3 Fig. 3: Simulation with the tail mounted at mid back level

TABLE I :

 I The geometric and mass parameters for the Human-Tail model with respect to Fig.1. Distances have units of metres and mass in kilograms.

	Segment (i)	h i	l i	w i	d i	m i
	Body (b)	0.997		0.15	1.8 (h) 78.2
	Arm (a)	1.11 0.225 0.0958		4
	Load (l)	1.23 0.354 0.193	0.15	0/5

ACKNOWLEDGEMENT

This research was conducted with funding from UKRI EPSRC project EP/T027746/1.We thank Etienne Burdet for valuable discussions.