David Eyers

Giovanni Russello

Toward unified and flexible security policies enforceable within the Cloud

Security engineering for any given application can usually be done in many different ways. There is often a tradeoff between usability (including efficiency) and the level of protection offered. Typically the risks are assessed by developers, and a particular approach is chosen, with the assumption that the design can stay fixed for some time. Adoption of Cloud computing will challenge the viability of this approach. Beyond the extra difficulties faced when doing security engineering within distributed systems, Cloud providers require a different threat model from selfhosted resources. They are best considered "trusted but curious" even if the curiosity is accidental on the Cloud provider's part. Some threats from such Cloud providers can be confounded through the use of cryptography, but doing so is overkill in terms of the performance penalty for many applications. To acquire the benefits of Cloud computing while minimising security risks, we believe that application developers should be provided with the ability to dynamically change the security enforcement technology in use by their software, balancing performance and security as they see fit. Recent cryptography research will significantly increase our ability to offer a runtime choice of contrasting security enforcement approaches without needing to modify the security policy. We present our initial research into this area, and outline our vision for the future.

Introduction

Application developers need to carefully consider the security engineering of their software. This is particularly true today, as so many devices are network accessible-and indeed need network functionality in order to operate at all-their exposed security surface area is larger than in the past days of isolated microcomputers.

Even software on single machines needs to interact with a number of local software components (broadly defined), simply due to the need to build on top of existing operating system and language runtime codebases.

Two broad types of data security model are Discretionary Access Control (DAC) and Mandatory Access Control (MAC)-see [1] for details. In DAC systems, the owners of protected resources are empowered to change the permissions of those objects, e.g., in Access control lists, capabilities and role-based access control (RBAC).

In MAC models, access control policy is enforced regardless of the desires of the owners of a protected resource. A common illustration is multi-level security models used in the military and other government organisations: data and principals are given security labels, and policy determines for any data access whether that access will be permitted as a function of the type of access and the labels of the principal and the data, e.g., policy may prevent a principal writing 'top secret' data into a 'classified' resource.

DAC schemes are often enforced by ensuring that code execution paths that access protected resources do permission checking before allowing such access. A risk of this approach is that it relates more to software code than the data it is trying to protect: in some cases access control checks may be accidentally omitted. In other cases this is due to control flow paths allowing implicit access to protected data.

MAC schemes are frequently implemented in a more directly data-centric manner. Since no code path should be able to circumvent the label-based protection, it is appropriate to use techniques to protect the data that may have higher run-time overheads, such as hardware-assisted memory protection. It is impractical to avoid having some trusted computing base (TCB) even in the strictest MAC schemes, but the TCB is ideally isolated entirely from the applications and data it is protecting (often it would be part of the operating system).

One potential approach to ensuring mandatory, data-linked protection against information leakage is to maintain the data in encrypted form, if the TCB is the only part of the code that possesses the decryption keys. Implementing MAC this way may allow for less effort being required to protect the target data: some application-level functionality, such as writing data into a database, might be able to be permitted, despite the data storage functionality not actually being contained within the TCB. This may lead to a more practical system than approaches that require expensive runtime interception of all protected data access.

Regardless of the mechanism used to enforce policy, generally accepted best practice is to abstract security policy away from application-specific implementation code. Widely available implementations of access control technologies such as XACML have helped make it easier to achieve this practice. Maintaining this sort of policy abstraction simplifies making access control policy modifications after software has been deployed.

Security engineering in distributed systems is significantly more complex than for software running on single hosts. However, widespread adoption of Cloud computing will cause distributed security engineering to be required within a growing proportion of applications. The terminology of IETF RFC 2904 [START_REF] Vollbrecht | IETF RFC 2904: AAA authorization framework[END_REF] includes separate notions of a policy decision point (PDP) and a policy enforcement point (PEP), which highlights the possibility to perform expensive policy checking in a different part of the distributed system than the software component that mediates access to a protected resource.

Enter Cloud computing

Cloud computing provides a challenging type of distributed system in which to deploy security-sensitive software. The challenge stems from the Cloud provider being a different organisation from the Cloud tenant, combined with the requirement that Cloud resources need to be accessed across a network. Beyond the need to run above a hypervisor in the first place, Infrastructure as a Service (IaaS) Cloud offerings need to manage the data travelling in a Cloud provider's network between instances of virtual machines, e.g., that host parts of a typical three-tier web application. Then, as Cloud deployment increasingly uses Platform as a Service (PaaS) offerings, a growing number of application components will be distributed in a way that exposes previously internal security considerations.

Cloud computing providers are most safely treated as "trusted but curious". The curiosity might well be accidental-a provider may leak data from the processes that they use to achieve data backups, for example. However the Cloud provider is clearly "trusted" in that outsourcing to an overtly malicious organisation makes no sense at all.

Put another way, if the primary objectives of computer security are to effect confidentiality, integrity, availability, then we are targeting systems that can provide integrity and availability, but through software or working practice errors, may fail to maintain complete confidentiality.

In this respect, Fully Homomorphic Encryption (FHE) represents the holy grail in Cloud security: FHE allows computers to perform arbitrary computation on encrypted data. FHE protects users' privacy from curious Cloud providers since they are unable to view the users' data. However, the first solution to FHE presented by Gentry [START_REF] Gentry | Fully homomorphic encryption using ideal lattices[END_REF] is very inefficient. Partially Homomorphic Encryption (PHE) schemes exist supporting limited computations on the encrypted data but in a more efficient way. PHE schemes have been used extensively for supporting search operations over encrypted databases in outsourced settings [START_REF] Song | Practical techniques for searches on encrypted data[END_REF][START_REF] Hacigümüs | Executing sql over encrypted data in the database-service-provider model[END_REF][START_REF] Golle | Secure conjunctive keyword search over encrypted data[END_REF][START_REF] Chang | Privacy preserving keyword searches on remote encrypted data[END_REF][START_REF] Wang | Efficient secure query evaluation over encrypted xml databases[END_REF][START_REF] Bösch | Conjunctive wildcard search over encrypted data[END_REF][START_REF] Popa | Cryptdb: protecting confidentiality with encrypted query processing[END_REF][START_REF] Curtmola | Searchable symmetric encryption: improved definitions and efficient constructions[END_REF][START_REF] Boneh | Conjunctive, subset, and range queries on encrypted data[END_REF][START_REF] Zhu | Peksrand: Providing predicate privacy in public-key encryption with keyword search[END_REF][START_REF] Dong | Shared and searchable encrypted data for untrusted servers[END_REF][START_REF] Shao | Proxy re-encryption with keyword search[END_REF]. The main issue of these approaches is that they enforce a very basic access control policy: if a user has a decryption key then she is allowed to access the whole database. We argue that more flexible security policies can be enforced if the mechanism for protecting the data from the Cloud provider is separated from the mechanism for controlling access to the data.

Contribution

This position paper describes our work to increase the flexibility of security in outsourced systems, by proposing a distributed architecture where data protection mechanisms are orthogonal to the security policy enforcement. We aim to allow developers to flexibly tradeoff between speed, simplicity and security for different parts of their applications without needing to rewrite their access control policy.

In particular, application developers can choose between enforcing security using access control barriers, or through the use of encryption. Using barriers will process data more quickly, but the policy enforcement infrastructure must be trusted to see the data that it is releasing to the principals. In the latter case, we extend how cryptographic protection is implemented, by utilising PHE algorithms to allow the policy enforcement point to remain oblivious to the content of the data being released, avoiding an undesired, additional TCB point within the overall distributed system.

Encrypted policy enforcement

There are several PHE-based solutions that offer encrypted storage of data while allowing basic search capabilities to be performed on the server side without the server learning anything about the plaintext data [START_REF] Song | Practical techniques for searches on encrypted data[END_REF][START_REF] Hacigümüs | Executing sql over encrypted data in the database-service-provider model[END_REF][START_REF] Golle | Secure conjunctive keyword search over encrypted data[END_REF][START_REF] Chang | Privacy preserving keyword searches on remote encrypted data[END_REF][START_REF] Wang | Efficient secure query evaluation over encrypted xml databases[END_REF][START_REF] Bösch | Conjunctive wildcard search over encrypted data[END_REF][START_REF] Popa | Cryptdb: protecting confidentiality with encrypted query processing[END_REF][START_REF] Curtmola | Searchable symmetric encryption: improved definitions and efficient constructions[END_REF][START_REF] Boneh | Conjunctive, subset, and range queries on encrypted data[END_REF][START_REF] Zhu | Peksrand: Providing predicate privacy in public-key encryption with keyword search[END_REF][START_REF] Dong | Shared and searchable encrypted data for untrusted servers[END_REF][START_REF] Shao | Proxy re-encryption with keyword search[END_REF]. However, these solutions assume all users have the same right to access data. Basically, these solutions lack access control mechanisms to enforce access policies for regulating the access of a user (or a group of users) to a particular subset of the stored data. To partially alleviate this problem, solutions such as the one described in [START_REF] Vimercati | Over-encryption: management of access control evolution on outsourced data[END_REF] have been proposed where access policies are encoded as a set of encryption keys. Only users possessing a key are authorised to access the data. The main drawback of this approach is that security policies are tightly coupled with the security mechanism. Therefore, any changes in the security policies require to generate new keys and to redistribute them to the users.

In our research, we argue that the security model used for controlling access to the data should be made disjoint from the mechanism used for protecting the data from the Cloud provider. For instance, most companies use as a security model for protecting their infrastructure variations of Role-Based Access Control (RBAC) [START_REF] Sandhu | Role-based access control models[END_REF]. In the RBAC model, access decisions are based on the role of the user making a access request. However, typical implementations of this model cannot be deployed on an infrastructure that is not fully trusted, such as Cloud environments because the information they deal with may leak information on the data they are protecting and the internal structure of the organisation. Similar considerations can be made for other MAC and DAC access control models-but for lack of space we focus on the RBAC model here.

We consider an Cloud scenario with outsourced security management involving two service providers: the Data Service Provider is responsible for storing the data; the AC Service Provider is responsible for the enforcement of access control policies. For reliability, the two services might be provided by different Cloud providers (although this is not a strict requirement for our approach). It is assumed that the Cloud providers are honest-but-curious, that is, they allow the components to follow the protocol to perform the required actions but curious to deduce information about the exchanged and stored data. Figure 1 provides an overview of our distributed architecture for separating policy enforcement from data protection mechanisms.

The responsibility of specifying policies and updating them is that of the Admin User. The Requester requests access to the data residing in the outsourced environment. The Company RBAC Manager is responsible for assigning a role to the requested user (that is, an Admin User or a Requester). The Server RBAC Manager is responsible for managing the encrypted role hierarchy graph. The Trusted Key Management Authority (KMA) generates and securely transmits the secret keys to the key store. An Admin User (i) gets a role from the Company RBAC Manager and then (ii) deploys the access policies to the Administration Point that (iii) stores the policies in the Policy Store. Meanwhile, the Company RBAC Manager sends the role hierarchy graph that is stored by the Server RBAC Manager (iv).

To request data, a query needs to be encrypted first (0). The Requester then (1) gets a role assigned by the Company RBAC Manager. Next, the Requester (2) sends the request to the Policy Enforcement Point (PEP) which (3) forwards the request to the Policy Decision Point (PDP). The PDP (4) fetches matching policies against the request, (5) collects the contextual information from the Policy Information Point (PIP), and (6) the role information. The PDP evaluates the access request and the contextual information against policies and sends the policy decision to the PEP [START_REF] Chang | Privacy preserving keyword searches on remote encrypted data[END_REF]. If the decision is a deny, then PEP usually drops communication or replies to the Requester with an error.If the decision is permit, the PEP (8) forwards the encrypted query to the Data Store. Finally, the PEP (9) forwards the query results to the Requester. The enforcement of encrypted RBAC policies is based on the ESPOON ERBAC system [START_REF] Asghar | Espoon: Enforcing encrypted security policies in outsourced environments[END_REF]. However, the idea presented in this position paper is to extend the functionality of the PEP to support communication with external service providers where the data is stored. The storage service can use several different types of data protection, independently of the access control model implemented in the AC Service Provider.

The degree of decoupling can be selected by the system designer, depending on their view of the security risk posed by the various different hosting organisations in use within the distributed system. If the trusted/untrusted environment division shown in figure 1 is too conservative for some parts of the application, 'untrusted' components can be moved to the 'trusted' side. Crucially, for the RBAC policies discussed here, this change in trust does not require the access control policy to be rewritten.

Future work and conclusion

In this paper we have discussed how Cloud computing environments have increased the number of participants in distributed access control applications, and how this can negatively impact security. Nonetheless, highest-grade encryption may be overkill for some parts of an application, where the security risks do not justify its use.

Our goal is to develop security technologies for Cloud computing that can flexibly change between software-based protection (i.e., access control monitors) and stronger protection encoded using encryption, without requiring the policy to be rewritten. We have presented an implementation of RBAC that uses the ESPOON ERBAC system, and illustrated how PHE solutions can provide a cryptography-based distributed RBAC enforcement environment. The same RBAC can be checked more cheaply using conventional access control monitors, working from an equivalent policy implementation. Our future work will increase the coverage of policy features that can be implemented using encryption, and to improve the performance of our techniques. We believe our notion of decoupling access control enforcement from the policy specification will be crucial to effect comprehensive security within Cloud computing.

Fig. 1 .

 1 Fig. 1. Our distributed architecture for enforcing RBAC in outsourced environments

Data Service Provider

Trusted Key Management Authority


Andreas Jaegermann

Timm J Filler

Michael Schoettner

Distributed Architecture for a Peer-to-Peer-based Virtual Microscope

Virtual microscopes are commonly used in medical education. They provide a platform for distributing whole slide images (WSI) with several GB size to exploring students. Even in courses with a few hundred students and dozens of WSI the network tra c may be high, but it will vastly increase, when the system is opened to access from the Internet. The same applies to user-generated content like interactive annotations (each student generates approx. 200 labels per term). In a collection that consists of several thousand WSI, which need to be annotated for training or quiz-based purposes, there will be millions of user contributions. In an abstract view users navigate through a universe of WSI and annotations and may meet other users watching the same or related WSI. This paper presents a distributed architecture build on PathFinder for Internet-based virtual microscopy addressing the challenges of distributing tightly connected data chunks on an overlay network consisting of random graphs.

Introduction

A virtual microscope is a system, which provides digitalized slides for a large number of simultaneously accessing clients, similar to geographic applications like Google Maps. Slide scanners are used to digitize glass slides and create proprietary slide file formats depending on the scanners' manufacturer [START_REF] García Rojo | Critical comparison of 31 commercially available digital slide systems in pathology[END_REF]. The file size varies with the dimensions of the scanned specimen and ranges from a few MB to several GB. Virtual microscopes have been developed more than a decade ago to fit the needs of pathologists and have been adopted for educational purposes in microscopic anatomy in the last few years [START_REF] Drake | Medical education in the anatomical sciences: The winds of change continue to blow[END_REF]. As the typical setup consists of a server accessing the file resources and delivering them on demand to any connected client via either proprietary communication protocols or http/ftp, the system's transmission capacity is obviously limited by the server's network connection. Usually, all systems are designed to work with classroomsized courses and some are capable of handling up to a few hundred clients connecting simultaneously. The number of virtual microscopes increased steadily, but nearly every solution su↵ers from one main disadvantage: if the number of histological slides in a collection exceeds a few hundred, the labeling process to provide students with detailed, qualified information about di↵erent structures is extremely time consuming for lecturers. However, the annotations created in a slide are essential to virtual microscopes because they extend the virtual microscope far beyond the capabilities of a real light microscope. Single cells, strata or complex tissue formations are examples of structures to be labeled. Not only are these annotations some explanations in an otherwise silent image, but rather do they provide a feedback on the personal learning progress for students. On the other hand, an increasing number of already validated annotations will help to evaluate new and varying annotations. Additionally, annotations can be used in online exams for automated evaluation.

In a common client/server setup the number of connecting clients is limited to a few hundred at maximum due to the hardware and connection requirements. Meeting more substantial requirements often leads to disproportional costs. To address these challenges we develop a system that supports a distributed architecture for transmitting digitized slides as well as a context-based user platform for real-time interaction.

To improve the scalability of virtual microscopes accompanied by an elevation of interactivity between users among themselves and the network, we transformed the typical client/server setup into a (managed) peer-to-peer architecture. Our solution is based on PathFinder, a peer-to-peer overlay network that relies on random graphs and provides an e cient combination of long range queries and single key-value lookups [START_REF] Bradler | Pathfinder: E cient lookups and e cient search in peer-to-peer networks[END_REF].

This paper is organized as follows. In Sect. 2 we present an overview of our distributed virtual microscope (DVM). Section 3 catches up with related work in the field of peer-to-peer systems. In Sect. 4 the advantages of PathFinder for our approach and the necessary adaptions are explained. Conclusions are presented in Sect. 5.

Architecture of the Distributed Virtual Microscope

The WSI are stored in tiles and a fully digitalized slide with a decent Z-stack in the highest magnification can easily produce up to 0.5 million tiles. A whole collection of a few thousand slides will lead to billions of images that need to be transmitted across the DVM along with corresponding annotations, messages and status information.

New WSI can only be stored in the network by selected nodes to ensure proper quality and compliant preparation.

Each node participating in the DVM has a standardized architecture and provides di↵erent services to the user and/or the network itself. It has to contribute a variable amount of storage capacity to be used by the DVM for the distribution of WSI. Additionally the user can store needed (or predictably needed) data. To assure data integrity the storage container acts like a black box and no standard user is allowed to modify any stored objects or store new objects.

The bottom most layer of a node (see Fig. 1) contains the overlay network responsible for handling joins and deletions of nodes. Additionally it detects and handles crashes as well as it adapts the network size. It manages the queries to physically locate data, nodes and users. The message service layer uses the overlay network to transmit messages between di↵erent users, users and nodes and among nodes themselves. Messages are generated in upper layers and may contain di↵erent types of information or requests. This service uses fingerprints and checkpointing to recover from a partial or complete loss of messages.

As the heart of a node the content management controller decides upon locally observed and from the neighborhood acquired data, what objects should be moved to or from the local storage container. By calculating performance values from network and storage parameters it can decide to ask neighbors for help while processing complex requests. In addition it is responsible for generating requests to increase the size of the immediate neighborhood if too much load is generated on the node and its existing neighbors.

The authentication service is tightly controlling user access and responsible for distributed authentication in case the authentication server is not available. Therefore signed key pairs from a trusted resource are created for each node. For distributed authentication each participating peer can check the certificate chain to decide if single requests should be executed or declined. As this is a only fallback mechanism to keep the network operational in case of a server failure no new accounts can be created at that time.

The next higher authority for each node is the sanity controller that has to make sure all needed local services are running and that the node has a working connection to a sane neighborhood.

On top there is just a graphical user interface to allow users to interact with the DVM. Slides can be selected, annotations can be created and messages can be send to other users.

Searchable Peer-to-Peer Overlay Network

Multicast protocols to transmit a tiled WSI were discarded as the data in DVM is no longer located at a single source and the complete transmission of a single WSI is, due to regions of interest, commonly not needed.

As we designed DVM to be a peer-to-peer (P2P) system build on hundreds of thousands of heterogeneously distributed nodes of varying performance, we were in need of a search that can be used to locate specific tiles of a WSI (a specific hash can be assigned to each tile) as well as processing exhaustive searches e.g. to find WSIs matching given criteria.

The decision to create a structured or an unstructured network while designing DVM was strengthened by the benefits of distributed hash tables (DHT). DHTs o↵er some advantages over unstructured P2P system (like Gnutella or Napster) as they include load balancing, e cient routing and resilience against node failures.

Although the scientific community has seen many implementations and enhancements to DHTs [START_REF] Stoica | Chord: A scalable peer-to-peer lookup service for internet applications[END_REF][START_REF] Rowstron | Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems[END_REF] all designs rely on randomizing hash functions for inserting and searching keys in the hash table. This hashing is the main advantage for the e cient value retrievals of DHTs for a given key.

Other systems on unstructured networks like SkipGraphs [START_REF] Aspnes | Skip graphs[END_REF], Mercury [START_REF] Ashwin | Mercury: Supporting scalable multi-attribute range queries[END_REF] and VoroNet [START_REF] Beaumont | Voronet: A scalable object network based on voronoi tessellations[END_REF] provide multiple-attribute range queries. Compared to DHTs they are less fault tolerant (or require more e↵ort to equalize) and are not as scalable (concerning the search performance for known hashes).

BubbleStorm [START_REF] Terpstra | Bubblestorm: Analysis of probabilistic exhaustive search in a heterogeneous peer-to-peer system[END_REF] is an overlay network capable of exhaustive searches in largescale heterogeneous environments with adjustable probabilistic guarantees. The underlying structure of a well connected multigraph where each node has an even degree is extremely resilient to node crashes, as they do not destroy the search paths, and highly e cient concerning multiple-attribute queries. The only thing missing is the e ciency of a value lookup (like in a DHT) if the hash is known. PathFinder [START_REF] Bradler | Pathfinder: E cient lookups and e cient search in peer-to-peer networks[END_REF] fills this spot by augmenting BubbleStorms random graphs with a deterministic lookup mechanism.

Distributed slides

After thoroughly comparing di↵erent approaches of overlay networks and DHT augmentations regarding query performance, routing and tra c overhead, we considered PathFinder to be a good starting point. The heterogeneous context of DVM regarding hardware, operating systems and network connections is incorporated into the topology of PathFinder. Designed as a connected multigraph PathFinder models this structure as a circular permutation only modified by JOIN, LEAVE and CRASH events of nodes and uses subgraphs of controlled size for data retrieval by solving the rendezvous problem. The proportionality of each nodes degree and its capacity leads to fixed size routing tables and locally controlled workload, which is highly appreciated. If a nodes workload increases, the DVM's content management service can simply request to add more nodes to the neighborhood.

The DHT-like hash lookups of PathFinder are realized by using two pseudorandom number generators (PRNG) that produce a deterministic sequence of numbers when initialized with a specific number. The first PRNG is used to calculate the number of neighbors each virtual node has by producing Poisson distributed numbers. The second one generates numbers that are treated as the node IDs of the neighbors for the current virtual node. This procedure enables each node to determine the neighbors for any node in the network without network communication. To find a path from the seeker u to node v containing the required information, the physical node responsible for u computes the neighbors of u (what is already accomplished, since they are contained in the routing table) and v, looking for matching neighbors while increasing the distance to u and v in each step by 1 if no match is found.

One key point in distributing slides is the connection between its tiles and the consequences this implies for the computed hash of the tiles. It is necessary that the hash for a tile can be calculated from the WSI it belongs to and its position therein (see Tab. 1). Additionally, we necessarily want to store multiple copies of a tile in the DVM to reduce the load on single nodes containing some or many popular tiles. To achieve this, we change the definition of a virtual node. In PathFinder a virtual nodes is located on exactly one physical peer. We augment the definition in a way that a virtual node can be spared over one or more physical nodes.

What needs to be changed in the original concept is that a virtual node has to keep track of the physical nodes it relies on. Therefore each physical node maintains a list of physical nodes sharing a virtual node with it. Incoming requests for an object can be passed from one physical node to his equally responsible neighbor if allowed by performance information from the content management service.

Further, a virtual node must be able to acquire more capacities as new physical nodes join the system or at least move some of its content to adjacent virtual nodes. The former is possible only if a new node joins as a direct neighbor and the latter is already implemented in PathFinder as this is just the creating of a new virtual node resulting in a modification of the hash space. The new virtual node can be moved to other physical nodes if required by means of performance.

Conclusion

In this paper we have presented DVM, a distributed virtual microscope based on the PathFinder overlay network. We showed that the combined strengths of e cient hash value lookups as well as e cient long range queries in a single overlay network made PathFinder the superior starting point for DVM. The integrated possibility to locally manage any nodes workload with respect to asynchronous connection bandwidths was a major argument, too. We have also presented DVM-specific extensions to PathFinders structure definition by augmenting the distribution of virtual nodes across physical nodes and choosing a proper basis for the hash function to reflect the correlation between di↵erent tiles and their position in a WSI. The random graph based overlay network constructed by PathFinder will provide optimized search results in the application scope of a distributed virtual microscope. Another advantage of our structure enhancement is that many operations can be implemented using parallel algorithms what will most probably lead to at least slightly increased performance. The development process of the distributed architecture will be finished shortly and practical testing will allow further evaluation, adaption and optimization from the gained experiences.

Fig. 1 .

 1 Fig. 1. Modular layered architecture of node in the DVM

Table 1 .

 1 Definition for Naming Tiles in DVM

	WSI Identifier Magfication Layer Z-Stack Layer Tile Position X Tile Position Y
	32 Bit	8 Bit	8 Bit	16 Bit	16 Bit


Ana Nunes
email: ananunes@di.uminho.pt

Rui Oliveira

José Pereira

AJITTS

Keywords:

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Optimistic concurrency control in distributed data processing systems is increasingly popular. In replicated database systems [START_REF] Correia | Akara: A flexible clustering protocol for demanding transactional workloads[END_REF][START_REF] Pedone | The database state machine approach[END_REF][START_REF] Kemme | Don't be lazy, be consistent: Postgres-r, a new way to implement database replication[END_REF], it allows concurrent transactions to execute at different sites regardless of possible conflicts. Conflict detection and resolution are performed at commit time, before the changes are applied to the database. In large scale, high throughput transactional systems such as Google Percolator [START_REF] Peng | Large-scale incremental processing using distributed transactions and notifications[END_REF] and OMID [START_REF] Yabandeh | A critique of snapshot isolation[END_REF], implementations of optimistic concurrency control with different isolation levels and locking policies are key to achieving radical scalability.

While optimistic concurrency control allows more concurrency and thus better use of resources than its counterpart, transactions that are later found to conflict are aborted and must be re-executed. Notice that the more transactions are allowed to execute concurrently, the more likely it is for conflicts to arise. Also, any transaction is vulnerable to being aborted by other transactions from the moment it starts to execute until is is certified: the longer it takes to execute and certify a given transaction, the more vulnerable it is. This is the caveat of most optimistic concurrency control strategies: when loaded, latency increases and fairness is compromised, particularly for long-running transactions [START_REF] Correia | Akara: A flexible clustering protocol for demanding transactional workloads[END_REF].

In contrast, conservative concurrency control is implemented by subjecting transactions to a priori conflict detection. In some of these protocols, conflict detection is done by associating queues to data partitions [START_REF] Kemme | Don't be lazy, be consistent: Postgres-r, a new way to implement database replication[END_REF][START_REF] Patiño-Martínez | Scalable replication in database clusters[END_REF][START_REF] Jiménez-Peris | Improving the scalability of fault-tolerant database clusters[END_REF][START_REF] Kemme | Processing transactions over optimistic atomic broadcast protocols[END_REF]. The queues are used to serialize transactions that access the same data partitions. The performance penalty imposed by the conservative strategy depends on the grain considered for concurrency control: if the grain is too fine, conflict detection will result in a delay before transaction execution; on the other hand, if the grain is too coarse, transactions that would not otherwise conflict are unnecessarily prevented from executing concurrently [START_REF] Correia | Akara: A flexible clustering protocol for demanding transactional workloads[END_REF].

It has been proposed that both approaches be combined by conservatively reexecuting previously aborted transactions, which mitigates this issue. However, if appropriate conflict classes cannot be used to ensure no conflicts occur during re-execution, the system will quickly be prevented from exploting optimism [START_REF] Correia | Akara: A flexible clustering protocol for demanding transactional workloads[END_REF]. Moreover, although most optimistic concurrency control protocols execute transactions as soon as these are submitted [START_REF] Pedone | The database state machine approach[END_REF][START_REF] Kemme | Don't be lazy, be consistent: Postgres-r, a new way to implement database replication[END_REF], it has been pointed out that the worst scenarios for optimistic concurrency control can be mitigated by limiting the number of transactions executing concurrently [START_REF] Correia | Akara: A flexible clustering protocol for demanding transactional workloads[END_REF]. Transaction scheduling on non-distributed settings using queue-theoretic models for automatically adjusting the maximum parallelism level has been studied [START_REF] Schroeder | How to determine a good multi-programming level for external scheduling[END_REF]. However, selecting the correct level of parallelism is not straightforward and can result in a severe limitation to maximum throughput.

In this paper we solve this problem with AJITTS, an adaptive just-in-time transaction scheduler. This mechanism minimize aborts while maximizing transaction throughput by computing the appropriate start time for each transaction. The intuition behind this proposal is simple: If a transaction must wait to be certified in the correct order, to ensure consistency in a distributed system, it is better that it waits prior to execution, as it is not susceptible to being aborted by conflicts with concurrent transactions. The implementation of this simple intuition does however imply that the system is continually monitored and that an appropriate execution start time is computed for each transaction.

The rest of this paper is structured as follows. In Section 2 we show that there is an ideal configuration for each workload, that improves performance regarding the basic optimistic protocol, introducing then the mechanism used to dynamically compute such configuration. In Section 3 we use traces obtained from the TPC-E workload running on a MySQL database server to simulate different workload scenarios and evaluate our proposal. Finally, Section 4 concludes the paper.

Approach

The main insight leading to our proposal is as follows: Since transactions are vulnerable to being aborted from the time execution starts until certification, in order to minimize the number of aborts, execution should start as late as possible. On the other hand, if certification goes idle because transactions at the head of the queue have not been completely executed, the throughput decreases. Our approach is thus based on reaching and maintaining the optimal level of queuing in the system: As low as possible to minimize aborts but as high as needed to ensure that certification doesn't go idle, to maximize throughput.

System model

To test this hypothesis, we assume an abstract model that captures key aspects of a distributed transaction processing system. First, we assume that transactions submitted to the system are totally ordered and placed at the tail of a queue in the not executed state. This models either a centralized queue at the transaction manager server [START_REF] Yabandeh | A critique of snapshot isolation[END_REF] or local replicas of a queue built by a group communication system [START_REF] Pedone | The database state machine approach[END_REF]. Because transactions must be certified in a conflict-equivalent order to the total order on which replicas agreed, the system can be modelled as a single queue in which transactions go through several states.

We then introduce a line in the queue that determines which transactions should start execution: all transactions before the line are not eligible to start executing, while all transactions between the line and the head of the queue that are in the not executed state are to be executed. Simply put, transactions are evaluated for execution whenever a transaction arrives to (i.e. is submitted) or leaves the queue (i.e. committed or aborted). Transactions can only be certified upon reaching the head of the queue and having completed execution, entering the certification state.

Conflict detection ensues: if the transaction was in the executed state, conflicting transactions in either executing or executed states are aborted and the transaction is immediately certified; if it was in the aborted state, the outcome is an abort. For certification, we assume snapshot isolation, which differs from serializability by considering only write/write conflicts [START_REF] Lin | Middleware based data replication providing snapshot isolation[END_REF]. This is used in the overwhelming majority of current RDBMSs and has also been favored in distributed transaction processing systems.

Impact of scheduling

Ideally, the line would be placed at such a position that each transaction completes execution just as it arrives at the head of the queue, minimizing the time spent in the executed state before reaching certification, thus minimizing its vulnerability to being aborted by others. However if the transaction reaches the head of the queue in either not executed or executing states, it cannot be certified until it finishes. Certification must occur in a conflict-equivalent order to the previously established total order, which is key to guaranteeing determinism in a distributed setting. As such, transactions running late cannot be overtaken by others, leaving certification idle.

Transactions can have widely varying execution times (i.e. duration), which should be considered when scheduling them. Let d t be the estimate of the duration of transaction t, which can be easily obtained from a database planner.

Assuming that the head of the queue corresponds to position 1, let

pos t = input • d t (1)
be the position in the queue after which transaction t will be executed. This means that transaction t will be executed when there are pos t -1 or less transactions ahead of it in the queue, which is the same as placing a line in the queue.

Notice that transaction t is not scheduled for a particular instant in absolute time: it is relative to the current inter-arrival rate of transactions at the head of the queue. This enables out-of-order execution: a small transaction will begin execution near the head of the queue, while a very large transaction will begin execution as soon as it is submitted.

The input parameter provides a simple way to adjust how early transactions should be executed: for the same estimated duration, a higher value of input means that the transaction will be executed earlier than with a lower value.

We then built an event-driven simulation of the abstract system model with the adjustable executuon start line. This simulation allows the position of the line that triggers execution to be adjusted, as well as to use different workloads, further described in Section 3. From this simulation we collect a number of statistics, namely: usable throughput, considering transactions that can be committed; share of transactions aborted due to concurrency conflicts; and latency at each state, from which we derive also end-to-end latency.

Figure 1 shows the latency breakdown for a particular workload (400 clients) while varying the input parameter. On the right hand, transactions are scheduled early, thus reducing the amount of time in the not executed state, shown in blue. In fact, an extreme setting of the parameter is equivalent to the baseline optimistic protocol, meaning that transactions are immediatly scheduled for exection and the entire impact of synchronization happens in the executed state. On the left, transactions are scheduled later, thus waiting an increased amount of time before execution, but waiting very little as executed (in brown). As expected, varying this parameter does not have an impact in execution duration (in red). As expected, we observe that overly delaying transaction execution has an impact in total latency.

Figure 2 shows a complete set of statistics for three different workloads. These workloads differ only in the number of concurrent clients submitting transactions. First, we observe that besides impacting end-to-end latency, the input parameter that determines when execution is started also impacts throughput and the abort rate leading to the following trade off:

-On the left, with a larger delay before execution, transactions arrive at the head of the queue but are not yet fully executed, thus stalling certification and leading to reduced throughput. However, the small delay to certification leads to a reduced number of concurrency aborts. -On the right, transactions are executed fairly ahead of time, thus avoiding stalling the queue. On the other hand, by having started early they become concurrent with a larger number of transactions and thus lead to an increased amount of rollbacks due to conflicts. Notice that, for example, if input is between 0.4 • 10 -3 and 0.9 • 10 -3 for 800 clients, throughput is sub-optimal because transactions are being executed too late. This can be confirmed by analyzing the transaction latency in the same interval. Also, for example for 200 clients, the abort rate steadily rises as input increases, but when input becomes larger than 1, the abort rate stabilizes at around 5%. This happens because after this point roughly all transactions are being executed as soon as they are submitted, equivalent to using DBSM [START_REF] Pedone | The database state machine approach[END_REF]. This effect occurs for any number of clients, it is just a question of using a large enough input.

Figure 3 shows similar results when, instead of varying the workload, we vary the resources available for execution. This leads to the time spent in the executing state growing. However, the same trade off holds. In short, we observe that there is an intermediate configuration that provides the best usable throughput with moderate latency. This is true regardless of the number of concurrent clients or the resources available to execute transactions. This optimal configuration is however different for different settings, which makes its configuration by the system developer unfeasible. As it varies with the workload, it is also impractical as a configuration parameter.

Adapting the workload

The question becomes how to determine an appropriate input value that provides optimal throughput without resorting to trial and error. A simple adaptation mechanism would be to simply start execution one position sooner whenever a transaction reaches the head of the queue in the not executed or executing states or one position later whenever it has to wait in the executed state or has been aborted. This approach was tested, but such an adaptation mechanism, while simple, causes oscillation, since such changes are too abrupt [START_REF] Aström | Feedback systems: An introduction for scientists and engineers[END_REF].

Let t state be the instant in which transaction t reaches state state. For any transaction t, s t = t not executed -t executing 0.2 0.4 0.6 0.8 1 measures how long transaction t had to wait to begin to execute since it was submitted, and q t = t certif ication -t executed measures how long transaction t had to wait after its execution was complete before reaching the head of the queue to be certified, henceforth simply referred to as pre-execution delay and queuing, respectively. Queuing is directly affected by whether transactions are executed sooner or later: on average, the former increases queuing while the latter decreases it. Let Q be a weighted cumulative rolling average of q and Q opt the optimal level of queuing for a system. An adaptive mechanism that reacts to the state of the queue can be defined using a proportional-integral-derivative controller [START_REF] Aström | Feedback systems: An introduction for scientists and engineers[END_REF] with Q as the sensor, Q opt as the set point and input as the system input [START_REF] Aström | Feedback systems: An introduction for scientists and engineers[END_REF] such that:

•
error = setpoint -sensor P value = Kp * error input+ = P value
Simply put, the error of the measured value (sensor) relatively to the desired value (setpoint) is used to update an input to the system (input) which will in turn impact the measured value, constituting the control feedback loop.

Kp is referred to as proportional gain, a tuning parameter that adjusts how the sensitivity of the controller, i.e., the magnitude of the adaptation relatively to the magnitude of the error. Several methods exist for selecting an appropriate value for Kp, from manual tuning to methods based on heuristics [START_REF] Aström | Automatic tuning of simple regulators with specifications on phase and amplitude margins[END_REF].

Because computing the position of the line relies on an estimated value for transaction duration, for which the expected value is the mean, depending on the variance of the population, selecting a set point of 0 would mean that several transactions would not finish its execution in time, leaving certification idle.

The key to finding Q opt is in comparing the bottom-right chart of Figure 2 which shows the ratio between the average queuing and the average duration of all transactions with the top-left chart showing throughput. Notice that the input values that achieve optimal throughput in the top-left chart match those for which the ratio in the bottom-right chart is roughly 1. Intuitively, selecting the set point to target average duration would mean that certification does not go idle and, consequently, that the rate at which transactions are certified is the same as the rate at which transactions arrive at the head of the queue which corresponds to optimal throughput but minimizing the size of the queue meaning a minimal abort rate. If deemed necessary, due to high variance in transaction duration, from the cumulative distribution function of transaction duration one can choose a value for the set point corresponding to a desired percentile: the higher the percentile of the chosen value, the higher the number of transactions that will have completed execution as expected.

Evaluation

Workload

TPC-E [START_REF]TPC Benchmark E -Standard Specification[END_REF] is a benchmark that simulates the activities of a brokerage firm which handles customer account management, trade order execution on behalf of customers and the interaction with financial markets. This analysis was based on tpce-mysql, 1 an open-source implementation of the TPC-E benchmark. This benchmark defines 33 tables across four domains: customer, broker, market and dimension and 10 main transaction types that operate across the domains. TPC-E's read/write transactions are: Market Feed (MF), Trade Order (TO), Trade Result (TR), Trade Update (TU) and Data Maintenance (DM). 2AJITTS was evaluated using a simple event-driven simulator that enables a profound analysis of each aspect of scheduling and concurrency control of replication protocols. The simulator processes execution traces obtained by running TPC-E like benchmark on a centralized MySQL3 database and then parsing the resulting binlog to generate the workload to test replication protocols. In essence, the simulator uses the following information from the binlog: the timestamps at which each transaction started, how long it took to execute each transaction and transaction write sets.

Another relevant feature of the simulator is that it allows the parallelization of the load generated by serial runs of TPC-E over the same database. In short, it does so by creating unique identifiers for each transaction and by manipulating timestamps making these relative to a reference instant. As a result, the load applied to the protocol under test can be easily scaled. Also, the applied load is not limited by resource constraints on the original MySQL database: there is no limit on the number of load units that can be applied in parallel.

The values of transaction duration extracted from the binlog reflect the penalty introduced by synchronization and locking in the MySQL engine when the benchmark is executed. A correction factor (β) can be calibrated by running the traces through the simulator with optimistic scheduling, without admission restriction and without re-execution, chosen such that the abort rate is close to 1%. The reason for this is that the sequence of transactions in the binlog has implicitly been proved to be conflict-free with the original values for transaction duration.

Let dur t be the duration extracted from the binlog for transaction t. The respective value to be used in the simulation is dur t = β * dur t .

The value of the correction factor depends on the benchmark load induced on MySQL. Therefore, the β used in the simulation is independent of the number of parallel traces used to fuel the simulator, as long as the load induced by each benchmark run was about the same. If using another set of traces, the beta must be recalculated. β is 0.2 for the traces used to evaluate AJITTS.

As discussed in Section 2, the set point should be chosen taking into consideration the distribution of transaction duration. In the results presented here, the set point used in AJITTS is the same as the average transaction duration of the given workload.

In order to simplify the implementation of AJITTS, instead of estimating the duration of each transaction, a line is placed on the queue for each type of transaction. The position of the line for a transaction of type MF, for example, is calculated as where d M F is an online estimate of the duration of MF transactions using a cumulative rolling average. While TPC-E already provides strictly defined transaction types, one could classify transactions in generic workloads by either considering the similarity in execution plans or, for example, the conflict classes accessed by transactions. Still, AJITTS can be implemented without this simplification, computing a line for each individual transaction.

line M F = input * d M F

Results

We compare AJITTS with OPT, a protocol with a standard optimistic scheduler. Simply put, OPT schedules each execution as soon as it is submitted. Using the TPC-E based workload described in Section 3.1, this is simulated by admitting at most one transaction per client, since clients are single-threaded. Notice that without this restriction, the number of concurrent transactions would be higher than allowed in the original benchmark.

Figure 4 compares OPT and AJITTS in terms of throughput and aborts for three workloads that differ only on the number of concurrent clients submitting transactions. Notice that even though AJITTS introduces delays on transaction executions, throughput is not only not adversely affected, but actually improved. Also, AJITTS clearly succeeds in significantly reducing the abort rate. In fact, a clear trend of further improvement can be observed in both charts as the load increases.

Figure 5 shows how the line positions per transaction type evolve during a run with a particular workload. Line positions are updated whenever the estimates for execution duration change or whenever the adaptation input parameter changes. The position of the line for each transaction type converges quickly: the Figure 6 shows how the different average durations (in red) influence the preexecution delay (in blue) when using AJITTS: again, TU transactions (TUa) are scheduled much earlier than others, while MF transactions (MFa), for instance, are only executed nearer the head of the queue. When compairing the results regarding, for example, MF transactions, the average time during which these are vulnerable to being aborted much smaller using AJITTS (110 ms) than using OPT (562 ms). This is also the case for TR and TO transactions. However, for TU transactions queueing actually increases using AJITTS. This is a consequence of ensuring that certification does not go idle. As expected, the net effect is still a reduced abort rate.

Considering different values of β shapes the workload: higher βs simulate less available resources and vice-versa. Figure 7 shows how AJITTS leverages available resources significantly better than OPT. In particular, the less available resources, the more OPT's throughput decreases relatively to AJITTS.

Conclusion

Although increasingly popular and often used, optimistic concurrency control may lead, with more demanding workloads, to a large number of conflicts and aborted transactions. This endangers fairness and reduces usable throughput. Fig. 6. Average latency breakdown using AJITTS and OPT: Pre-execution delay (blue), execution latency (red), and queueing for certification (brown). Columns MFa, TRa, TOa and TUa refer to an execution of the AJITTS protocol, while the others refer to an execution of the OPT protocol.

Previous attempts at tackling this problem required workload-specific configuration and would still impact peak throughput [START_REF] Correia | Akara: A flexible clustering protocol for demanding transactional workloads[END_REF].

With AJITTS, the adaptive just-in-time transaction scheduler, we provide a solution that does not require workload specific configuration and adapts in runtime to current workload and resource availability conditions. This is achieved by delaying transaction execution, for each transaction individually based on the estimated time to complete and current queueing within the system.

AJITTS was then evaluated using a simulation model driven by traces from TPC-E running on MySQL, demonstrating that it clearly outperforms the baseline protocol. In fact, in addition to reduced aborts, it actually improves peak throughput even if it throttles transaction execution. This is the consequence of using available resources better.

Fig. 1 .

 1 Fig.1. Average latency breakdown with a varying scheduler parameter: Pre-execution delay (blue), execution latency (red), and queueing for certification (brown).

Fig. 2 .

 2 Fig.2. Effect of the input value on throughput, the abort rate, transaction latency and on the ratio between average transaction queueing and average duration for different numbers of clients.

Fig. 3 .

 3 Fig.3. Effect of the input value on throughput, the abort rate, transaction latency and on the ratio between average transaction queueing and average duration for different distributions of transaction duration.

Fig. 4 .

 4 Fig.4. Throughput and abort rates using OPT and AJITTS for different numbers of clients.

Fig. 5 .

 5 Fig. 5. Evolution of the position of the lines during a particular run.

Fig. 7 .

 7 Fig. 7. Throughput and abort rates for OPT and AJITTS for different βs.

https://code.launchpad.net/perconadev/perconatools/tpcemysql

The Data Maintenance transaction type operates exclusively on a separate group of tables. As such, it is not relevant for this analysis and is essentially omitted from the discussion that follows.

http://www.mysql.com

Acknowledgements

This work is part-funded by: ERDF -European Regional Development Fund through the COMPETE Programme (operational programme for competitiveness) and by National Funds through the FCT -Fundação para a Ciência e a Tecnologia (Portuguese Foundation for Science and Technology) within project Stratus/FCOMP-01-0124-FEDER-015020.


Kevin Pinte
email: kpinte@vub.ac.be

Andoni Lombide Carreton

Elisa Gonzalez Boix

Wolfgang De Meuter
email: wdmeuter@vub.ac.be

Ambient Clouds: Reactive Asynchronous Collections for Mobile Ad Hoc Network Applications

Keywords: collection, mobile ad hoc network, peer-to-peer application, language abstraction

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The steep increase in popularity of mobile devices has yielded a market for applications running on mobile ad hoc networks (MANETs). MANET applications assume no fixed infrastructure and spontaneously engage in interaction when the devices they run on are in communication range. These applications communicate over wireless networks, for example Wi-Fi Direct or Bluetooth. Using mainstream programming languages such applications are usually conceived as distributed object-oriented applications, coordinating their actions by exchanging objects.

In MANETs, the number of devices participating in an interaction is not known a priori, but it varies as devices join and leave the network as they move about. Typically, applications are interested in communicating only with a specific group of those remote objects which are discovered at runtime. For example, in a chat application, users can join or leave a chat room at any moment in time. In order to reflect the communication state of the users in the chat room and to allow communication with them, the programmer has to manually maintain a collection of remote objects. In MANETs, the nature of the connection to the devices hosting these objects is volatile. Such a collection of remote objects is continuously fluctuating because of the volatile nature of the connections to the devices hosting these objects.

At the software level, we can identify two ad hoc ways commonly used to implement such collections. A first approach when using a distributed objectoriented programming language is to discover and store the remote objects in a local collection. Once discovered, the programmer must manually iterate over the collection's content and communicate with the stored remote objects by means of remote method invocations or asynchronous message passing. It is the programmer's responsibility to make sure that these objects are still connected by making use of try-catch blocks or other failure handling mechanisms.

A second strategy is to employ an event-based distributed model such as a publish/subscribe architecture. In this case, the collections become groups of objects classified under a topic and potentially filtered on their content using predicates [START_REF] Eugster | The many faces of publish/subscribe[END_REF]. However, publish/subscribe middlewares abstract the network connectivity between the publisher and subscriber. This obliges programmers to bypass the middleware periodically to detect whether the publishers are still connected and verify that their published objects are still "alive" (i.e., in case of a crash). Additionally, the events signalled by the publish/subscribe middleware must still be manually converted to additions and removals on local collections. This hinders straightforward and e cient querying and composition of such collections.

None of both solutions provides adequate means to create, maintain and query collections of remote objects. This leads the programmer to write boilerplate code that is scattered throughout the actual application code. In this paper, we propose ambient clouds: a reactive asynchronous collection abstraction to maintain and query collections of remote objects in MANET applications. Additionally, ambient clouds provide reactive standard query operators. Querying or composing ambient clouds using these operators constructs a chain of dependent result collections. The operators observe the collections they were applied to. Changes in either the composition of the constituent elements are implicitly and incrementally reflected throughout the chain of dependent result collections.

In the remainder of this paper, we show the problems that led us to explore ambient clouds (section 2), how ambient clouds tackle these problems at a high level, and how programmers can use ambient clouds to quickly develop mobile applications (section 3). We explain how ambient clouds are implemented (section 4) and how they are used in the collaborative drawing application, called weScribble (section 5). Subsequently, we discuss related work (section 6) and, finally, conclude this paper and suggest how we intend to improve ambient clouds in the future (section 7).

Problem Statement

In what follows, we detail the issues that can be identified when developing applications that deal with collections of remote objects. We illustrate the problems using a chat application as a running example.

The chat application presents the user with the option to create a chatroom or join an existing one. When the user enters a chatroom, he or she is presented with a list of users that joined this room and are currently in communication range. The application also shows the messages that belong to the chatroom and users can choose to ignore messages from certain other users.

P1. Volatile collections. MANET applications discover other applications and services running in the environment to interact with them. The applications typically maintain a collection of "currently available" objects in which the application is interested. Since devices hosting MANET applications can appear and disappear at any moment in time, we regard these collections of remote objects as highly volatile. Therefore, specifying the contents of the collection extensionally (i.e., on a per-element basis) is problematic as the contents of the collections can change at any point in time. With current techniques, the programmer is left to manually synchronise the contents of these volatile collections of remote objects.

To interact with these collections, the programmer typically uses constructs such as indices and iterators. These constructs do not map well to volatile collections of remote objects because the collection changes underneath them. For example, the chat application maintains a list of currently co-located users. As users move about, the composition of this list changes dynamically.

P2. Querying and composing collections. A natural operation on collections of objects is to apply operators to compose them with other collections or query them. For example, the chat application applies a filter operation on the list of users to display only those that reside in the chosen chatroom.

Querying and composing volatile collections is not an atomic action: collections can grow or shrink several times while a composition or query is being computed. Furthermore, when employing asynchronous method invocation to communicate with remote objects, the results of a query over the elements of a collection may not be available instantaneously.

As the composition of a collection evolves, the initial result of applying an operator diverges from the current state. This means that programmers have to write additional code to ensure results from applying operators remain synchronised with the collection they were applied to. It also implies that compositions of collections resulting from queries over such volatile collections are themselves volatile. This requirement is a serious deviation from the traditional notion of querying collections, where the result of a query does not bear any relationship to the target collection.

P3. Propagating state changes. When employing a distributed object-oriented model objects are either exchanged "by copy" or "by reference". This results in a collection of respectively local copies of the objects published by a remote device, or remote references to these objects. In the former case, whenever the owner changes an object, the changes should be propagated to all the copies spread across the network. In the latter case, whenever an object is changed, collections containing a reference to this object should be notified of this change. For example, when a user changes his nickname in the chat application, this should be reflected in the buddy list on the applications of other users.

This propagation of state changes can be accomplished through, for example, a publish/subscribe framework. However, changes made to an object can result in it being removed from or added to the result of a certain operation on the collection. In the chat application, a user that decides to move to another chat room changes the "current chat room" property. This change causes some collections to remove this user object from the old chat room, while other collections add the user to the new chat room. Thus, collections containing remote objects should have a means to subscribe to changes on properties of their constituent objects.

Ambient Clouds

In this section, we introduce a novel abstraction representing collections of remote objects named ambient clouds. Ambient clouds are an object-oriented abstraction that tackles the issues outlined above by combining event-driven interaction, based on a publish/subscribe model, and reactive programming.

We solve problem P1 by allowing developers to specify an ambient cloud of a certain type of objects they want to interact with. The type of the objects acts as an initial filter in order to collect objects of interest. An event-driven API signals events whenever an object is added to or removed from the ambient cloud. To address problem P2 we provide reactive standard query operators to query and compose ambient clouds. Any computation performed using such an operator is re-executed as the collection changes. The operators automatically handle asynchronous operations. This does not require breaking the abstraction of the collections by looking at their contents at a certain moment in time. To tackle P3 we model object pass-by-copy and pass-by-reference semantics using reactive objects and reactive isolates. These are object-oriented reactive values of which the state changes over time. These changes are observed and the eventdriven API signals state modification events to the collections in which they are contained.

AmbientClouds at Work

We have prototyped ambient clouds in the distributed programming language AmbientTalk [START_REF] Van Cutsem | AmbientTalk: object-oriented event-driven programming in mobile ad hoc networks[END_REF]. AmbientTalk is an experimental programming language tailored towards developing peer-to-peer applications that operate in MANETs.

We now describe the language constructs provided to create and interact with ambient clouds in the context of the chat application.

Ambient clouds coarsely collect objects related to the application using a type tag. Type tags are a lightweight classification mechanism to categorise remote objects explicitly by means of a nominal type. They can best be compared to a topic in publish/subscribe terminology or marker interfaces in Java. Below we create the ambient cloud of all co-located users using the cloudOf: construct and passing it the ChatUser type tag as argument.

deftype ChatUser; def users := cloudOf: ChatUser

We define an object representing a user of the chat application by means of the object: construct. A user has an identifier, a nickname and an attribute containing the name of the selected chatroom. To publish this object in the network as a ChatUser we use the export:as: construct of AmbientTalk.

def me := object: { def id := 123; def nickname := "Kevin"; def currentChatroom := "purple" }; export: me as: ChatUser Ambient clouds continuously synchronise their composition as devices move in and out of range. Users that leave communication range are automatically removed from the collection, users that appear in range are added automatically.

Note that users are represented as regular objects, they are published in the network by reference. The ambient cloud of users thus contains remote objects references that can be contacted by sending it asynchronous messages. Later we will show an example of an ambient cloud of remote objects passed by copy.

We further refine the ambient cloud of users using the reactive standard query operators we provide for ambient clouds: In this example we first filter the ambient cloud of users, selecting only users that reside in the same chatroom. To this end we use the where: method that takes a predicate as argument. After the filter operation we select the nicknames of the users using the select: operator, for example to display them in the GUI.

In both query operations, we send an asynchronous message to the remote user object (expressed by the operator in AmbientTalk). An asynchronous message send immediately returns a future, which is a placeholder for the actual return value of the message. In the above example the equals function waits for the result of the message 1 to be available before computing the equality and in turn immediately returns a future. The where: and select: operators will automatically wait for futures to resolve with their values and process the results of asynchronous operations as they become available. If an element was removed before an asynchronous operation on that element was completed, the operation is cancelled and the result ignored.

The collections that result from applying operators to an ambient cloud transparently maintain a dependency relation to that ambient cloud. Any time the composition of the ambient cloud is changed or any time one of its constituents is changed, the operation incrementally updates the result collection. The result collection is never totally recomputed, rather dependent elements are either added to the result collection, removed from it or updated. Figure 1 shows the dependency chain that corresponds to the above code snippet. Figure 1 shows the progression of events when the users ambient cloud changes. First, in step T 1 , a new user is discovered and added to the users ambient cloud. In step T 2 , the filter operation that generated the usersInRoom ambient cloud is then applied to this user object. Since the user has also joined the "purple" chatroom, the user is added to the resulting collection. In step T 3 , the dependent nicknames ambient cloud is extended with the nickname of the user by applying the select operator to the added user object.

Aside from addition, two more events cause the operators to update their results. Figure 2 depicts the progression of events when a user is removed from the users ambient cloud in step T 4 to T 6 . The user and nickname are subsequently removed from the dependent result collections. Starting from step T 7 a user switches from the "purple" to the "orange" chatroom. The filter operation is reapplied and causes the user and nickname to be automatically removed from the resulting collections. The reactive standard query operators are defined as methods on ambient clouds. We also provide a language extension that provides syntactic sugar for writing queries and turns them into first-class language constructs. In the example below we illustrate how to group chat messages with their authors. In the example above we define the ambient cloud of chat messages starting from line 2. In line 3 we group the ambient cloud based on a userId attribute using the groupBy: operator. This results in an ambient cloud of groups of messages identified by the userId. These groups of messages are again ambient clouds which in turn can be queried. Starting from line 4 we associate users with a group of messages using the join:on: operator. The join is performed based on matching the user's identifier with the identifier attribute in the message. This can be used to ignore the messages of a certain user in the chatroom.

Implementation

As mentioned before, ambient clouds are implemented in AmbientTalk and available to the programmer as a library. Ambient clouds are built on top of the Java Collections Framework2 and combine AmbientTalk's service discovery mecha-nism (based on IP multicasting) with reactive sets containing reactive values. Note that AmbientTalk is an actor-based language. Execution (e.g., updating ambient clouds) within an actor is sequential and actors communicate by sending asynchronous messages that are processed in sequence by the receiving actor.

Reactive Asynchronous Collections

The implementation of ambient clouds is based on an reactive asynchronous collection framework that employs local Java collections. Reactive asynchronous collections are conceived as the combination of observable collections with reactive asynchronous operators. Our model consists out of the following collection types:

-set: no ordering, no duplicates (similar to Java HashSet) -list: ordering, duplicates allowed (similar to Java ArrayList) -sorted set: sorting, no duplicates (similar to Java TreeSet)

The programmer uses an event-driven API to install event handlers in order to observe a collection. These event handlers are executed when elements are either added or removed from the collection. This example creates a new reactive set and registers two event handlers that write a message to the standard output every time an element is added (line 2) or removed (line 3) from the collection.

Additionally, the collections can be observed for changes to their constituents. When a reactive value is added to a collection, the collection installs an event handler to observe the state of the value. When the state of the reactive value changes, the collection in turn notifies its own observers. The example below shows an event handler that writes a message to the standard output whenever the state of a constituent reactive value changes. whenever: s changed: { |el| system.println("changed " + el) } Ambient clouds are created by connecting the AmbientTalk discovery protocol to reactive sets. Below we show the skeleton code to manually construct the ambient cloud of users in the chat application. In line 1 we first create an empty reactive set. In line 2 we install an event handler to discover objects of type ChatUser, using the built-in whenever:discovered: construct of AmbientTalk. When an object of this type is discovered, it is added to the set in line 3. Two more event handlers are installed in lines 4 and 5. The first event handler is installed using AmbientTalk's built-in when:disconnected: construct and removes the element from the set when a disconnection occurs. The last event handler is executed when the state of the user object is altered and notifies the set of this change.

Reactive Objects and Isolates

In the implementation of ambient clouds we modelled objects as reactive values.

A reactive value (also behavior ) is a value that changes over time [START_REF] Bainomugisha | A survey on reactive programming[END_REF]. We regard objects as composite values of which the state can be altered over time using field assignment.

Programmers can publish objects in the network either by reference or by copy, as reactive objects or as reactive isolates. Reactive objects are transferred by reference, remote peers obtain an observable remote object reference. An observable remote object reference consists of a proxy object and a reference to the remote object. Reactive collections can install observers on the proxy object which are notified when the state of the object is modified locally. This causes operations applied on the object to be recomputed. Reactive isolates are special objects that have no surrounding lexical scope (i.e., similar to structs, but they can have methods defined on them). This way, they can be easily copied over the network and cached in the ambient clouds of remote peers. The underlying implementation locally observes the state of an isolate and implicitly synchronises state across the copies on di↵erent devices. Note that race conditions are prevented by the actor system of AmbientTalk, as explained in section 4. Of course, the programmer should bear in mind that the remote peer may be disconnected and that the copy is temporary out of sync. Any time the state is synchronised, the observers registered by reactive collections are notified.

In subsection 3.1 we showed an example of a user represented by a regular object. The example below shows the creation of a chat message represented by an isolate. Reactive objects and isolates are key in the design of ambient clouds since changes to their state triggers re-computation of dependent results.

Reactive Standard Query Operators

The reactive standard query operators rely heavily on the observable features of the collections to incrementally update their results. They update their results based on three kinds of events: the insertion and removal of elements in a collection and state changes in the elements. When an operator is applied to a collection, the necessary observers are installed and the operator is applied on all elements already contained in the collection. For example, consider the implementation of the where: operator below. The operator takes a predicate as argument. In line 2 we create a new collection that contains the results of applying the operator. In lines 3 and 4 we first apply the predicate to all elements already contained in the collection and add them if that application succeeds. In lines 5 and 6 we install a handler that applies the predicate to elements added to the collection and add them to the result collection if necessary. In line 7 we install a handler that removes elements from the result as they are removed from the collection. The handler in lines 8 and 9 reapplies the predicate to an element if its state was changed, possibly removing the element from the result if applying the predicate no longer succeeds. This code clearly shows that the automatic updates of the result are incremental. The execution of the event handlers in lines 5, 7 and 8 concern the addition, removal or update of a single element in the result. In line 10 we register the parent of the result to be the collection over which we applied the operator. In line 11 we finally return the resulting collection.

Note that this code was was simplified for demonstration purposes. It does not deal with the possibility that an asynchronous operation is performed in the predicate application.

The weScribble Application

In this section, we validate ambient clouds in the implementation of a collaborative drawing application for the Android platform, called weScribble3 . The application allows users to dynamically participate in drawing sessions with other people co-located. Aside from mobile Android devices and wireless ad hoc connections between these devices, no other infrastructure is assumed.

At startup, weScribble presents the user with a list of drawing sessions available in the environment with an indication of the amount of people drawing in each session. The user can either join a session or choose to create a new one. A drawing session consists of a number of participants and a shared canvas on which they can draw. When a user joins a drawing session, the application synchronises the canvas with the existing participants to fetch the shapes that were already drawn and displays them on the screen. The user can then draw on the canvas of that session and the changes to the canvas are propagated to the other participants of the session whose canvas is updated accordingly. If a user temporarily disconnects from the network, he or she can keep drawing. Upon reconnection, those changes are synchronised with the other users in the session. We display the names of all discovered users in the GUI. Using the eventdriven API we install two event handlers to show and hide names as they are added to or removed from the ambient cloud. Users can choose to ignore shapes from other users by enabling a toggle in the GUI. We continue by defining an observable set containing the users that we choose to ignore.

def ignoredPainters := ObservableSet.new(); def ignore(painter) { ignoredPainters.add(painter) }

We now obtain the ambient cloud of shapes (represented by isolates) to display by joining the ambient cloud of all shapes with the di↵erence of the ambient cloud of users and the users to ignore. Note here that adding users to the ignoredPainters set causes its shapes to disappear from the shapes ambient cloud. Finally we draw the relevant shapes and install event handlers to draw and hide shapes as the ambient cloud is updated.

shapes.each: { |s| GUI.draw(s) }; whenever: shapes extended: { |s| GUI.drawShape(s) }; whenever: shapes reduced: { |s| GUI.removeShape(s) }; whenever: shapes changed: { |s| GUI.redrawShape(s) };

Discussion

In the implementation of weScribble ambient clouds tackle the issues outlined in section 2 as follows.

-P1 : Ambient clouds automatically maintain collections of co-located users and the shapes they created. The programmer is relieved from manually synchronising the contents of these collections with the network situation. -P2 : We used reactive standard query operators over ambient clouds to filter users based on the drawing session. We also associate users with their shapes, filtering out shapes of users we wish to ignore without having to manually update these results when users appear or disappear. -P3 : When users change the colour of their shapes, these changes are automatically propagated to the applications of other users by means of reactive isolates. If users change their nickname this is automatically reflected in the user lists of the other users using reactive objects.

Related Work

The problems around group abstractions for mobile applications is well established. However, most of the research focuses on group communication which is not the focus of this work. In this section, we discuss related work that focuses on organising remote objects in intermittently connected peer-to-peer applications.

Distributed Asynchronous Collections (DACs) [START_REF] Eugster | Distributed Asynchronous Collections: Abstractions for publish/subscribe interaction[END_REF] were originally devised as a way to marry publish/subscribe systems to traditional collection frameworks. They allow developers to subscribe to additions and removals that occur in the collections. However, DACs o↵er no support for tracking the connectivity of publishers that publish objects, so the programmer still has to track this manually.

Tuple spaces [START_REF] Gelernter | Generative communication in Linda[END_REF] allow distributed parties to publish tuples to a conceptually shared memory. LIME [START_REF] Murphy | LIME: A middleware for physical and logical mobility[END_REF] even allows distinct tuple spaces to merge if users are close to each other and allows programmers to define reactions on the appearance or disappearance of tuples. Tuple spaces do not support the direct modification of tuples: tuples have to be removed first and new versions reinserted later. This requires application developers to write additional code to watch these remove/insert event pairs individually. Additionally, there is no support for creating a data structure from a tuple space, which forces programmers to update the derived collections manually.

Ambient references [START_REF] Van Cutsem | Ambient references: addressing objects in mobile networks[END_REF] allow discovering and communicating with homogenous groups of references to objects in the environment that change over time. This abstraction takes care of monitoring any disconnections and reconnections in the environment and even allows developers to take a snapshot of the current state. Ambient references do not allow programmers to react on objects, joining, leaving or being modified in the group. Additionally, they can not be composed, nor queried.

M2MI [START_REF] Kaminsky | Many-to-many invocation: a new object oriented paradigm for ad hoc collaborative systems[END_REF] introduces handles that denote a dynamic group of remote Java objects of the same interface and omnihandles that refer to all proximate objects of a certain interface. However, is not possible to react to state changes in the objects referred to by an omnihandle, nor is there support for querying.

Microsoft's Reactive Extensions for .NET [START_REF]The reactive extensions for[END_REF] allows processing events by modelling them as streams of values on which standard query operators are defined. The di↵erence with our work is that we define these standard query operators on object-oriented collections instead of event streams.

Reactive programming [START_REF] Bainomugisha | A survey on reactive programming[END_REF] is a paradigm that represents a program as a data flow graph based on the notion of time-varying values, which form nodes in the graph. If an operation is applied to a time-varying value, the operation is inserted as a node in the graph with a dependency edge to the time-varying value. When a time-varying value changes, dependent computations are automatically reexecuted by propagating the change through the graph. We discuss the relation between reactive programming and our work in section 7.

Conclusion and Future Work

In this paper, we introduced ambient clouds: an object-oriented abstraction that automatically maintains collections of remote objects. These ambient clouds support reactive standard query operators that implicitly update their results as changes in the underlying ambient clouds occur. Together they relieve the programmer from re-implementing the common patterns when dealing with (1) volatile collections of remote objects, (2) querying and composing these collections and (3) propagating state changes to derived collections.

We have implemented a MANET application called weScribble using ambient clouds to illustrate how ambient clouds circumvent these problems in a fully functional collaborative drawing application.

As possible avenues for future work, we wish to further extend our reactive collection framework with other collection types such as a hash map or tree structures. Additionally, unlike our model, in reactive programming languages, there are no special reactive operations. Every operation that depends on a reactive value is implicitly lifted to the reactive level. Currently, on our reactive asynchronous collections, special query operators are used to process changes. We are integrating our collections into a reactive programming language to reduce manual lifting.

  def usersInRoom := users.where: { |user| equals(user currentChatroom(), me.currentChatroom) }; def nicknames := usersInRoom.select: { |user| user nickname() }

Fig. 1 .

 1 Fig. 1. Dependency tree of the ambient clouds in the chat application

Fig. 2 .

 2 Fig. 2. Removing a user from the ambient cloud and changing the chatroom attribute of a user

1

  deftype ChatMessage; 2 def messages := cloudOf: ChatMessage 3 groupBy: { |msg| msg.userId } 4 join: usersInRoom 5 on: { |msg, user| 6 equals(msg.userId, user id()) }

1

  def users := ReactiveSet.new(); 2 whenever: ChatUser discovered: { |user| 3 users.add(user); 4 whenever: user disconnected: { users.remove(user) }; 5 whenever: user changed: { users.notifyChangeObservers(user) }}

  def aMessage := isolate: { def text := "Hello!" def userId := 123 }

Fig. 3 .

 3 Fig. 3. The weScribble Android application

  names.each: { |n| GUI.showInList(n) }; whenever: names extended: { |n| GUI.showInList(n) }; whenever: names reduced: { |n| GUI.removeFromList(n) }

  deftype Shapes; def shapes := cloudOf: Shapes join: (painters.except: ignoredPainters) on: { |shape, painter| s.painterId == p.id }

By annotating the message send with Due(t), a timeout t (in milliseconds) can be specified for the resulting future.

AmbientTalk is entirely implemented in Java and runs on top of the JVM. Java classes and objects can be accessed from within AmbientTalk and vice versa[START_REF] Cutsem | Linguistic symbiosis between event loop actors and threads[END_REF].

def s := ObservableSet.new();

whenever: s extended: { |el| system.println("added " + el) };

whenever: s reduced: { |el| system.println("removed " + el) }

WeScribble is available from Google Play at http://bit.ly/eOxpLg.