Guillaume Laville
email: guillaume.laville@univ-fcomte.fr

Kamel Mazouzi

Christophe Lang

Laurent Philippe

Nicolas Marilleau
email: nicolas.marilleau@ird.fr

Using GPU for Multi-agent Soil Simulation

Keywords: multi-agent systems, GPU, parallel computing

Multi-Agent Systems (MAS) can be used to model systems where the global behavior cannot be uniformly represented by standard techniques such as partial differential equations or linear systems because the system elements have their own independent behavior. This is, for instance, the case in complex systems such as daily mobility in a city for example. Depending on the system size the computing power needs for the MAS may be as big as for more traditional linear numerical systems and may need to be parallelized to fully represent real systems. Graphical Processing Units (GPU) have already proven to be an efficient support to execute large linear programs. In this paper we present the use of GPU for the execution of Sworm, a multi-scale MAS system. We show that GPU computing can be efficient in that less regular case and when the agent behavior is simple. We advocate for a wider use of the GPU in Agent Based Models in particular for multi-scale systems with work distribution between the CPU and GPU.

I. INTRODUCTION

Physical systems are often modeled by mathematical representations and their behavior simulated by dynamic differential equations. This is possible when the behavior of the elements of the system is uniformly driven by the same law, but when these elements have their own behavior, the modeling process is too complex to rely on this approach. Multi-Agent Systems (MAS) is a recognized approach to model and simulate systems where individuals have an autonomous behavior that cannot be simulated by the evolution of a set of variables driven by mathematical laws. MAS are often used to simulate natural or collective phenomenons whose actors are too numerous or various to provide a unified algorithm describing the system evolution. The agent-based approach is to divide these complex systems into individual, self-contained entities with their smaller set of attributes and functions. But, as for mathematical simulations, when the size of the Multi-Agent System increases the need of computing power and memory also increases. For this reason, multi-agent systems should benefit from the use of distributed computing architectures. Clusters and Grids are often identified as the main solution to increase simulation performance but Graphical Processing Units (GPU) are also a promising technology with an attractive performance/cost ratio.

Conceptually an Agent Based Model (ABM) is a distributed system as it favors the definition and description of large sets of individuals, the agents, that can be run in parallel. Most of the agent-based simulators are however designed with a sequential scheme in mind and these simulators seldom use more than one core for their execution. Due to simulation scheduling constraints, data sharing and exchange between agents and the huge amount of interactions between agents and their environment, it is indeed rather difficult to distribute an agent based simulator to take advantage of new multi-threaded computer architectures. Thus, guidelines and tools dedicated to MAS paradigm and HPC is now a need for other complex system communities. Note that, from the described structure (large number of agents sharing data), we can conclude that MAS would more easily make good use of many-cores computing than from other kinds of parallelism.

Another fact that advocates for the use of many-core in MAS is the growing need for multi-scale simulations. Multiscale simulations explore problems with interactions between several scales. The different scales use different granularities of the structure and potentially different models. Most of the time the lower scale simulations provide results to higher scale simulations. In that case the execution of the simulations can easily be distributed between the local cores and a many-core architecture, i.e. a GPU device.

We explore in this paper the use of many-core architectures to execute many-core simulations. Our case study is the Sworm simulator that aims at reproducing effects of earthworms on bacteria dynamics in a bulked soil. In Section ?? of the paper we present the work related to MAS and parallelization with a special focus on many-core use. We give an overview of the Sworm simulator in Section ?? and we detail its GPU implementation in Section ??. We present the experiments and results in Section ?? then we conclude on the possible generalization of our work.

II. GPU AND MULTI-AGENT SYSTEMS A. Agent-Based Simulations

Agent-Based systems are often used to simulate natural or collective phenomenons whose actors are too numerous or various to provide a simple unified algorithm describing the studied system dynamic [?]. The implementation of an agent based simulation usually starts by designing the underlying Agent Based Model (ABM). Most ABM are based around a few types of entities: Agent, Environment and Interaction Organization [?]. In the complex system domain, the environment often describes a real space, its structure (e.g. matter organization in soils) and its dynamics (e.g. organic matter decomposition). It is a virtual world in which agents represent studied entities (e.g. biotic organisms) evolving. The actual agent is animated by a behavior that can range between reactivity (only react to external stimuli) and cognition (lives its own process alongside other individuals). Interaction and Organization define functions, types and patterns of communications of their member agents in the system [?]. Note that, depending on the MAS, agents can communicate either directly through special primitives or indirectly through the information stored in the environment.

Agent based simulations have been used for more than one decade to simulate complex systems and have proved their interest in various scientific communities. Nowadays generic agent based frameworks are promoted such as Repast [?] or NetLogo [?] to implement simulations. Many ABM such as the crown model representing a city-wide scale [?] tend however to require a large number of agents to provide a realistic behavior and reliable global statistics. Moreover, an achieved model analysis needs to run many simulations identified into an experiment plan to obtain enough confidence in a simulation. In this case the available computing power often limits the simulation size and the result range thus requiring the use of parallelism to explore bigger configurations.

For that, three major approaches can be identified: 1) parallelizing experiments plan on a cluster or a grid (one or few simulations are submitted to each core) [?], [?] 2) parallelizing the simulator on a cluster (the environment of the MAS is split and run on several distributed nodes) [?], [?] 3) optimizing simulator by taking advantage of computer resources (multi-threading, GPU, and so on)[?] In the first case, the experiments are run independently of one another and only the simulation parameters change between two runs. A simple version of an existing simulator can thus be used. It does not imply model code changes except for Graphical Unit Interface extracting as the experiments does not run interactively but in batch. In the second and the third case, model and code modifications are necessary. Only few frameworks however introduce distribution in agent simulation (Madkit [?] or MASON [?]) and parallel implementations are often based on the explicit use of threads using shared memory [?] or cluster libraries such as MPI [?].

Parallelizing a multi-agent simulation is however complex due to space and time constraints. Multi-agent simulations are usually based on a synchronous execution of time steps by the agents that share the same environment. At each time step, numerous events (space data modification, agent motion) and interactions between agents happen. Distributing the simulation on several computers or grid nodes thus implies to guaranty a distributed synchronous execution and coherency, which often leads to poor performances or complex synchronization problems. Multi-cores execution or delegating part of this execution to others processors as GPUs [?] are usually easier to implement since all the threads share the data and the local clock.

Different agent patterns can be adopted in an ABMs such as cognitive and reactive ones [?]. Cognitive agents act on the environment and interact with other agents according to a complex behavior. This behavior takes a local perception of the virtual world and the agent past (a memory characterized by an internal state and belief, imperfect knowledge about the world) into account. Reactive agents have a much systematic pattern of action based on stimuli response schemes (no or few knowledge and state conservation in agent). The evolution of the ABM environment, in particular, is often represented with this last kind of agents. As their behavior is usually simple, we propose in this paper to delegate part of the environment and of the reactive agents execution to the graphical processing unit of the computer. This way we can balance the load between both CPU and GPU execution resources.

In the particular case of multi-scale simulations such as the Sworm simulation [?] the environment may be used at different levels. Since the representation of the whole simulated soil area would be costly, the environment is organized as a multi-level tree of small soil cubes which can be lazily instantiated during the simulation. This allows to gradually refine distribution details in units of soil as agents progress and need those informations, by using a fractal process based on the bigger-grained already instantiated levels. This characteristic, especially for a fractal model, could be the key of the distribution. For instance, each branch of a fractal environment could be identified as an independent area and parallelized. In addition Fractal is a famous approach to describe multi-scale environment (such as soil) and its organization [?]. In that case the lower scale simulations can also be delegated to the GPU card to limit the load of the main (upper scale) simulation.

B. Introduction to GPU computing

Graphics Processing Unit devices are based on a massivelyparallel hardware architecture, which allows the execution of a big amount of floating point instructions at the same time and their computing power is often measured in hundred of GFlops. These units were originally designed to be used by the graphic driver for multimedia [?] or graphic processes. The last few years saw however the apparition of new generations of graphic cards based on more general purpose execution units. These units can be programmed using GPGPU platforms to solve various problems in HPC applications such as linear algebra resolutions. They can be used both for dense problems, such as CuBLAS, a GPU implementation of the BLAS library, MAGMA [?] and sparse ones such as [?][?]. These applications are based on matrix manipulations where a set of operations is applied multiple times on each input data. The same kind of treatments are used in geometric computations which also suit the GPU particularly and yield to big performance gains.

These matrix-based data representation and SIMD computations are not so straightforward in Multi-Agent Systems, where data structures and algorithms are tightly coupled to the described simulation. However, works from existing literature show that MAS can benefit from these performance gains on various simulation types, such as traffic simulation [?], cellular automatons [?], mobile-agent based path-finding [?] or genetic algorithms [?].

An application-specific adaptation process was required in the case of these MAS: some of the previous examples are driven by mathematical laws (path-finding) or use a natural mapping between a discrete environment (cellular automaton) and GPU cores. Unfortunately, this mapping often requires algorithmic adaptations in other models but the experience shows that the more reactive a MAS is the more adapted its implementation is to GPU.

C. MAS Implementation on GPU

The first step in the adaptation of an ABM to GPU platforms is the choice of the language. On the one hand, the Java programming language is often used for the implementation of MAS due to its availability on numerous platforms or frameworks and its focus on high-level, object-oriented programming. On the other hand, GPU platforms can only run specific languages as OpenCL or CUDA. OpenCL (supported on AMD, Intel and NVIDIA hardware) better suits the portability concerns across a wide range of hardware needed the agent simulators, as opposed to CUDA which is a NVIDIAspecific library.

OpenCL is a C library which provides access to the underlying CPUs or GPUs using an asynchronous interface. Various OpenCL functions allow the compilation and the execution of programs on these execution resources, the copy of data buffers between devices, or the collection of profiling information.

This library is based around three main concepts:

• the kernel, which represents a runnable program containing instructions to be executed on the GPU. • the work-item (or task), which is analogous to the concept of thread on GPU, in that it represents one running instance of a GPU kernel. • the work-group (or task-group) which is a set of workitems sharing some memory to speed up data accesses and computations. Synchronization operations such as barrier can only be used across the same work-group. Running an OpenCL computation consists in launching numerous work-items that execute the same kernel. The workitems are submitted to a submission queue to optimize the available cores usage. A calculus is achieved once all these kernel instances have terminated.

The number of work-items used in each work-group is an important implementation choice which determines how many tasks will share the same cache memory. Data used by the work-items can be stored as N-dimensions matrices in local or global GPU memory. Since the size of this memory is often limited to a few hundred of kilobytes, choosing this number often implies a compromise between the model synchronization or data requirements and the available resources.

In the case of agent-based simulations, each agent can be naturally mapped to a work-item. Work-groups can then be used to represents groups of agents or simulations sharing common data (such as the environment) or algorithms (such as the background evolution process).

III. THE MIOR MODEL

The MIOR [?] model was developed by the GEODES Team of IRD (ex UMMISCO) to simulate local interactions in a soil between microbial colonies and organic matters. It reproduces each small cubic units (0.002) of soil as a MAS.

Multiple implementations of the MIOR model have already been realized, in Smalltalk and Netlogo, in 2 or 3 dimensions. The last implementation, used in our work and referenced as MIOR in the rest of the paper, is freely accessible online as WebSimMior1 .

MIOR is based around two types of agents: (i) the Meta-Mior (MM), which represents microbial colonies consuming carbon and (ii) the Organic Matter (OM) which represents carbon deposits occurring in soil.

The Meta-Mior agents are characterized by two distinct behaviors:

• breath: the action converts mineral carbon from the soil to carbon dioxide CO 2 that is released in the soil. • growth: by this action each microbial colony fixes the carbon present in the environment to reproduce itself (augments its size). This action is only possible if the colony breathing needs where covered, i.e. enough mineral carbon is available. These behaviors are described in the following algorithm ??. Since this simulation takes place at a microscopic scale, a large number of these simulations must be executed at each macroscopic simulation step to model realistic-sized unit of soil, despite the small computation cost of each individual simulation.

IV. MIOR IMPLEMENTATION ON GPU

As a starting point, we realized a simple GPU implementation of the MIOR simulator, with only minimal changes to the CPU algorithm. Execution times showed the inefficiency of this approach, and highlighted the necessity of adapting the simulator to take advantage of the GPU execution capabilities. In this part, we show the main changes which were realized to adapt the MIOR simulator on GPU architectures.

A. GPU Architecture of the MIOR model

Each MIOR simulation is represented by a work-group, and each agent by a work-item. A kernel is responsible of the life cycle process of each agent of the model. It is executed by all work-items of the simulation on their own gpu core.

The usage of a work-group for each simulation allows to easily execute multiple simulations in parallel, as shown on figure ??. Thus it becomes possible to exploit all the cores at the same time by taking advantage of execution overlap possibilities provided by OpenCL, even if an unique simulation is to small to use all the available GPU cores. However, the maximum size of a work-group is limited (512), which only allows use to execute one simulation per workgroup when using 310 threads (number of OM in the reference model) to execute the simulation.

The usage of the GPU to execute multiple simulations is initiated by the CPU. The later keeps total control of the simulator execution flow. Thus, optimized scheduling policies (such as submitting kernels in batch, or limiting the number of kernels, or asynchronously retrieving the simulation results) can be defined to minimize the cost related to data transfers between CPU and GPUs.

B. Data structures translation

The adaptation of the MIOR model to GPU requires the mapping of the data model to OpenCL data structures. The environment and the agents are represented by arrays of structures, where each structure describes the state of one entity. The behavior of these entities are implemented as OpenCL functions to be called from the kernels during execution.

Four main data structures are defined: (i) an array of MM agents, representing the state of the microbial colonies. (ii) an array of OM agents, representing the state of the carbon deposits. (iii) a topology matrix, which stores accessibility information between the two types of agents of the model (iv) a world structure, which contains all the global input data (metabolism rate, numbers of agents) and output data (quantity of CO 2 produced) of the simulation.

These data structures are initialized by the CPU and then copied on the GPU.

The world topology is stored as a two-dimension matrix which contains OM indexes on the abscissa and the MM index on the ordinate. Each agent walks through its line/column of the matrix at each iteration to determinate which agents can be accessed during the simulation. Since many agents are not connected this matrix is sparse, which introduces a big number of useless memory accesses. To reduce the impact of these memory accesses we propose a compacted, optimized representation of this matrix based on [?], as illustrated on the figure ??. Since memory allocations are impossible yet in OpenCL and only provided in the lastest revisions of the CUDA standard, these matrices are statically allocated to handle the worst-case scenario where all OM and MM are linked, since the actual occupation of the matrix cells cannot be deduced without some kind of preprocessing computations. The compact representation considers each line of the matrix as an index list, and only stores accessible agents continuously, to reduce the size of the list and the number of non productive accesses.

C. Critical resources access management

One of the main issue in a MIOR model is to ensure that all the microbial colonies will have an equitable access to carbon resources, when multiple colonies share the same deposits. Access synchronizations are mandatory in these cases to prevent conflicting updates on the same data that may lead to calculus error (e.g. loss of matter).

On a massively parallel architecture such as GPUs, this kind of synchronization conflicts can however lead to an inefficient implementation by enforcing a quasi-sequential execution. It is necessary, in the case of MIOR as well as for other ABM, to ensure that each work-item is not too constrained in its execution.

From the sequential algorithm 1 where all the agents share the same data, we have developed a parallel algorithm composed of three sequential stages separated by synchronization barriers. This new algorithm is based on the distribution of the available OM carbon deposits into parts at the beginning of each execution step. The three stages, illustrated on figure ??, are the following:

1) distribution: The available carbon in each carbon deposit (OM) is equitably dispatched between all accessible MM in the form of parts. 2) metabolism: Each MM consumes carbon in its allocated parts for its breathing and growing processes. 3) gathering: Unconsumed carbon in parts is gathered back into the carbon deposits. This solution suppresses the data synchronization needed by the first algorithm and thus the need for synchronization barriers.

Distribution

D. Termination detection

The termination of a MIOR simulation is reached when the model stabilizes, and no more CO 2 is produced. This detection can be done either on the CPU or the GPU.

In the first case, it is the CPU which controls the GPU simulation process: (i) the CPU starts the execution of a simulation step on the GPU. (ii) Once this step is finished, the CPU retrieves the GPU data, and determines if another iteration must be launched or if the simulation has terminated. This approach allows a fine-grain control over the GPU execution, but it requires many costly transfers as each iteration results must be sent from the GPU to the CPU. In the case of the MIOR model, these costs are mainly due to the inherent PCIexpress port latencies, rather than to bandwidth limitation, since data sizes remains rather small, in the order of few dozens of Megabytes.

In the second case the termination detection is directly implemented on the GPU: The CPU does not have any feedback while the simulation is running, but retrieves the results once the kernel execution is finished. This approach minimizes the number of transfers between the CPU and the GPU.

V. EXPERIMENTS

In this section we present several MIOR GPU implementations using the distribution/gathering process described in Section ?? and compare their performance on two distinct hardware platform; i.e two different GPU devices. Five incremental MIOR implementations were realized with an increasing level of adaptation for the algorithm: In all cases, we choose the average time over 50 executions as a performance indicator.

• the GPU 1.0 implementation is a direct implementation of the existing algorithm and its data structures where data dependencies were removed and using the noncompact topology representation described in Section ?? • the GPU 2.0 implementation uses the previously described compact representation of the topology and remains otherwise identical to the GPU 1.0 implementation. • the GPU 3.0 implementation introduces the manual copy into local (private) memory of often-accessed global data, such as carbon parts or topology information. • the GPU 4.0 implementation is also a variant of the GPU 1.0 implementation which allows the execution of multiple simulations for each kernel execution. • the GPU 5.0 implementation is a multi-simulation of the GPU 2.0 implementation, using the execution of multiple simulations for each kernel execution as for GPU 4.0

The two last implementations -GPU 4.0 and GPU 5.0illustrate the gain provided by a better usage of the hardware resources, thanks to the driver execution overlap capabilities. A sequential version of the MIOR algorithm, labeled as CPU, is provided for comparison purpose. This sequential version is developped in Java, the same language used for GPU implementations and the Sworm model.

For these performance evaluations, two platforms are used. The first one is representative of the kind of hardware which is available on HPC clusters. It is a cluster node dedicated to GPU computations with two Intel X5550 processors running at 2.67GHz and two Tesla C1060 GPU devices running at 1.3GHz and composed of 240 cores (30 multi-processors). Only one of these GPU is used in these experiments, at the moment. The second platform illustrates what can be expected from a personal desktop computer built a few years ago. It uses a Intel Q9300 CPU, running at 2.5GHz, and a Geforce 8800GT GPU card running at 1.5GHz and composed of 112 cores (14 multi-processors). The purpose of these two platforms is to assess the benefit that could be obtained either when a scientist has access to specialized hardware as a cluster or tries to take benefit from its own personal computer. The charts show that for small problems execution times of all implementations are very close. This is because the GPU implementation does not have enough threads (representing agents) for an optimal usage of GPU resources. This trend changes after scale 5 where GPU 2.0 and GPU 3.0 take the advantage on the GPU 1.0 and CPU implementations. This advantage continues to grow with the scaling factor, and reaches a speedup of 10 at the scale 10 between the fastest single-simulation GPU implementation and the first, naive one GPU 1.0.

Multiple trends can be observed in these results. First, optimizations for the GPU hardware show a big, positive impact on performances, illustrating the strong requirements on the algorithm properties to reach execution efficiency. These charts also show that despite the vast difference in numbers of cores between the two GPUs platforms the same trends can be observed in both case. We can therefore expect similar results on other GPU cards, without the need for more adaptations. Figure ?? illustrates the execution time for only one kernel. It shows that for small numbers of simulations run in parallel, the compact implementation of the model topology is faster than the two-dimension matrix representation. This trends reverse with more than 50 simulations in parallel, which can be explained either by the non linear progression of the synchronization costs or by the additional memory required for the access-efficient representation.

Figure ?? illustrates the execution time of a fixed number of simulations. It shows that for a small number of simulations run in parallel, the costs resulting of program setup, data copies and launch on GPU are determinant and very detrimental to performance. Once the number of simulations executed for each kernel grows, these costs are counterbalanced by computation costs. This trend is more marked in the case of the sparse implementation (GPU 4.0) than the compact one but appears on both curves. With more than 30 simulations for each kernel, execution times stalls, since hardware limits are reached. This indicates that the cost of preparing and launching kernels become negligible compared to the computing time once a good GPU occupation rate is achieved.

VI. CONCLUSION

This paper addresses the issue of complex system simulation by using agent based paradigm and GPU hardware. From the experiment on an existing Agent Based Model of soil science (Mior model) we intend to provide useful information on the architecture, the algorithm design and, the data management to run Agent based simulations on GPU. The first result of this work is that adapting the algorithm to a GPU architecture is possible and suitable to speed up agent based simulations. Coupling CPU with GPU seems even to be an interesting way to better take advantage of the power given by computers and clusters: cognitive agents can be run on the CPU and reactive agents or environment be run on the GPU. Note that simulations of reactive agents, with a simple behavior, give interesting and efficient results whereas the running of cognitive agent (such as social agents) on GPU are too complicated and less adapted to this kind of execution. From our point of view this adaptation process is lighter than a traditional parallelization on distributed nodes and not much difficult than a standard multi-threaded parallelization, since all the data remains on the same host and can be shared in central memory. The OCL adaptation also enables a portable simulator that can be run on different graphical units. Even using a mainstream card as the GPU card of a standard computer can lead to significant performance improvements. This is an interesting result as it opens the field of inexpensive HPC to the ABM community.

In this perspective, we are working on a generalization of these tools to other multi-agent models based around reactive computations. One first challenge is the definition of common, efficient, reusable data structures, such as grids or lists. Another goal of this solution is to provide easier means to control the distribution of specific processes on CPU or GPU, to allow the easy exploitation of the strengths of each platform in the same multi-agent simulation.

ACKNOWLEDGMENT

The authors would like to thanks the Mésocentre de calcul de Franche-Comté, which provided the computer facilities used for the computations described in the paper.

Fig. 1 .

 1 Fig. 1. Execution distribution retained on GPU

Fig. 2 .

 2 Fig. 2. Compact representation of the topology of a MIOR simulation

(Fig. 3 .

 3 Fig. 3. Decomposition in OpenCL kernels of one MIOR parallel execution cycle.

Fig. 4 .Fig. 5 .

 45 Fig. 4. CPU and GPU performance on a Tesla C1060 node

Fig. 6 .Fig. 7 .

 67 Fig. 6. Execution time of one multi-simulation kernel on the Tesla platform

http://www.IRD.fr/websimmior/


Nicolas Anciaux

Luc Bouganim

Thierry Delot
email: thierry.delot@inria.fr

Sergio Ilarri
email: silarri@unizar.es

Leila Kloul

Nathalie Mitton

Philippe Pucheral

Opportunistic Data Services in Least Developed Countries: Benefits, Challenges and Feasibility Issues

According to many studies, IT should become a key facilitator in establishing primary education, reducing mortality or supporting commercial initiatives in Least Developed Countries. The main barrier to the development of IT services in these regions is not only the lack of communication facilities, but also the lack of consistent information systems, security procedures, economic and legal support, as well as political commitment. In this paper, we propose the vision of an infrastructure-less data platform well suited for the development of innovative IT services in Least Developed Countries. We propose a participatory approach, called Folk-IS, where each individual implements a small subset of a complete information system thanks to highly secure, portable and low-cost personal devices as well as opportunistic networking, without the need for any form of infrastructure. In this paper, we focus on the exploitation and feasibility analysis of the Folk-IS vision. We also review the technical challenges that are specific to this approach.

INTRODUCTION

Least Developed Countries (LDCs) are 50 countries with nearly 1 billion people, which meet UN criteria in terms of poverty, human resource weaknesses and economic vulnerability. LDCs have no global access to the Internet and are more than ever left by the wayside with respect to Information and Communication Technologies (ICT). Does this mean that e-services are a superfluous luxury for LDCs? On the contrary, several reports [START_REF] Coceres | Information and Communication Technologies for Development -Guest Editors' Introduction[END_REF][START_REF]The Role of ICT in Advancing Growth in Least Developed Countries -Trends, Challenges and Opportunities[END_REF][START_REF] Rossi | IT in Emerging Markets[END_REF] make evident that ICT are called to play a catalytic role in these countries: ICT can help to achieve universal primary education, promote gender equality and empower women, reduce child mortality, combat HIV and other diseases, ensure environmental sustainability, and develop a global partnership for development.

However, the challenge of making e-services practical and affordable still remains. While 60% of the population in LDCs is already covered by a mobile cellular signal, only 0.5% has a mobile broadband subscription and a 3G service is offered only in at most 25% of the LDCs, very often at a prohibitive cost [START_REF]The Role of ICT in Advancing Growth in Least Developed Countries -Trends, Challenges and Opportunities[END_REF]. Hence, mobile phones in these areas are primarily feature phones used for voice and SMSs. Several innovative solutions are thus based on the use of mobile phones and text messages to address specific issues like keeping track of vaccine cold chains [START_REF] Chaudhri | Monitoring Vaccine Cold Chains in Developing Countries[END_REF], improving agriculture [START_REF] Sahilu | Designing Distributed Agricultural Information Services for Developing Countries[END_REF], or easing administrative procedures [START_REF] Ndou | E-Government for Developing Countries: Opportunities and Challenges[END_REF], but cannot be generalized to the broader scope of datadriven applications. Major industrial actors like Google (project Loon for All) and Facebook (Internet.org) are also conducting pioneering projects in this field, showing the potential for new applications and business in these areas. However, providing general data services in LDCs faces many obstacles which go far beyond low connectivity: severe lack of IS infrastructure, high initial investment, difficulty to maintain the system operational, reluctance to use the system due to security concerns, etc.

According to Non-Governmental Organizations (NGOs), four main requirements must be met to build a practical technical solution: (1) privacy protection: this is a major prerequisite due to local opaque practices and the lack of any security infrastructure (coercive laws, secured servers, trusted authorities, etc.), leading to a self-enforcement of privacy principles; (2) immediate personal benefit: because of the lack of strong economical or political incentives to impose the solution in the field, an immediate benefit must be provided to each user; (3) self-sufficiency: the solution must not rely on an hypothetic improvement of the existing software and hardware infrastructure; and (4) very low deployment cost: the usual scale being a few dollars per user. Besides this, users' empowerment is known to be crucial to make the solution sustainable in LDCs, and its maintenance should ideally generate a source of revenue for new local jobs.

In [START_REF] Anciaux | Trusted Cells: A Sea Change for Personal Data Services[END_REF], we proposed the vision of trusted cells, a data platform for personal data services where the shared infrastructure (typically the Cloud) is untrusted, while personal devices (such as smart phones, tablets or set-top boxes) are trusted execution environments. In this paper, we revisit this vision with the goal of providing data services to the inhabitants of LDCs. We propose a new paradigm, that we call Folk-enabled Information System (Folk-IS), based on a fully decentralized and participatory approach, where each individual implements a small subset of a complete information system without the need for a shared networked infrastructure. As trusted cells, Folk-IS builds upon the emergence of highly-secure, portable and low-cost storage and computing devices, called hereafter Smart Tokens. Here, however, the focus is on the low-cost of ownership, deployment and maintenance, and on the absence of a networked infrastructure. In Folk-IS, smart tokens have the capability to host the digital history of their owners and to exchange information in a privacypreserving manner. This enables people to transparently and opportunistically perform data management and networking tasks as they physically move, so that IT services are truly delivered by the crowd.

The potential advantages are important for the inhabitants (develop economics activities, hold a digital folder, communicate with friends, with NGOs or administrations, etc.), for the community (have communication means with inhabitants used to feed cultural programs or launch eadmin procedures like census, detect epidemics, etc.), and for the NGOs (conduct monitoring programs, consult/fill inhabitants folders when visiting them, etc.).

Rural Communities Connected World Internet Network

Folk-node

Folk-Net

Figure 1. Folk-enabled information system

We do not argue that Folk-IS is the ultimate solution. The future of IT in LDC will probably be multiform, the problem being important and complex enough to leave room for complementary initiatives. Folk-IS has the salient characteristics to enable a smooth and incremental deployment of an information system in a purely infrastructure-less context while taking advantage of existing elements of infrastructure, if any, to improve its own behavior.

In [START_REF] Anciaux | Folk-IS: Opportunistic Data Services in Least Developed Countries[END_REF], we presented our overall Folk-IS vision. This paper details this vision and shows that this paradigm technically makes sense, conforms to the requirements mentioned above and opens important and exciting research challenges for the database community.

REPRESENTATIVE ICT INITIATIVES IN LDCs

Applying ICT in developing countries has recently attracted considerable attention, reflected in recent special issues, such as [START_REF] Coceres | Information and Communication Technologies for Development -Guest Editors' Introduction[END_REF][START_REF] Rossi | IT in Emerging Markets[END_REF]. Several of the proposed applications aim at making use of mobile ICT services to resolve key challenges such as providing content that is locally relevant and mitigating access barriers linked to literacy and language [START_REF]VOIce-based Community-cEntric mobile Services for social development (VOICE)[END_REF]. However, when developing data-driven solutions for LDCs, important difficulties arise. The coverage of mobile phones in LDCs is increasing, but phones are primarily used for voice and SMSs, not for datadriven applications. Sir Tim Berners-Lee mentioned a recent study that showed that in Mozambique "using just 1GB of data can cost well over two months wages for the average citizen"1 . According to many analysts, this situation cannot evolve rapidly due to a combination of intrinsic barriers, not only technical, but also economical and organizational [START_REF] Brewer | The Case for Technology in Developing Regions[END_REF].

Many isolated initiatives have been launched with specific strategies for getting around these barriers, and propose adhoc solutions for specific problems. In relation to health issues, for example, we could mention FoneAstra, CVDMagic, NextDrop, and mWash. FoneAstra [START_REF] Chaudhri | Monitoring Vaccine Cold Chains in Developing Countries[END_REF] is a low-cost sensing system using mobile phones to keep track of vaccine cold chains. CVDMagic [START_REF] Singh | CVDMagic: A Mobile Based Study for CVD Risk Detection in Rural India[END_REF] proposes the use of mobile-based approaches to detect Cardio-Vascular Diseases (CVD) in India. NextDrop2 provides SMS alerts indicating when a tap will have water, at least 60 minutes in advance. Finally, mWash 3 and [10] consider the problem of collecting and disseminating information to ensure a safe access to sanitized water. Other interesting topics tackled in relation to developing countries are related to agriculture [START_REF] Sahilu | Designing Distributed Agricultural Information Services for Developing Countries[END_REF], and e-government [START_REF] Ndou | E-Government for Developing Countries: Opportunities and Challenges[END_REF], among others; see [START_REF] Murugesan | Mobile Apps in Africa[END_REF] for more examples of interesting ICT applications for developing countries. These solutions address key issues in developing countries and bring actual improvements. However, despite their undisputed interest, these initiatives usually exploit only text messages for exchanging data, and remain confined to specific applications. Their generalization also faces other barriers like the lack of global information system infrastructures, of security procedures, and economic and political support.

Supporting more powerful form of data-driven applications to provide global e-services undeniably requires improved network connectivity.

However, according to many analysts, even if increasing the number of "urban" spots would be an obvious solution, their deployment is very challenging as it would require more base stations, and hence more energy with collateral difficulties, like the need to carry gas-oil and protect it against theft [START_REF]The Role of ICT in Advancing Growth in Least Developed Countries -Trends, Challenges and Opportunities[END_REF]. To overcome the limitations of Internet coverage, several pioneering proposals do not rely on a hypothetic future improvement of the infrastructure, but propose new alternatives. Thus, proposals [START_REF] Pentland | DakNet: Rethinking Connectivity in Developing Nations[END_REF][START_REF] Seth | Low-Cost Communication for Rural Internet Kiosks Using Mechanical Backhaul[END_REF] exploit mobile ad-hoc networks to provide asynchronous connectivity for dataoriented services. Specifically, in DakNet [START_REF] Pentland | DakNet: Rethinking Connectivity in Developing Nations[END_REF] mobile access points are mounted on physical means of transportation (e.g., buses, motorcycles) to transport data or information requests from one place to another. The related approach in [START_REF] Seth | Low-Cost Communication for Rural Internet Kiosks Using Mechanical Backhaul[END_REF] suggests the use of buses and cars to carry data between villages and Internet gateways. In relation to these proposals, the so-called Delay-Tolerant Networks (DTNs) [START_REF] Fall | A Delay-Tolerant Network Architecture for Challenged Internets[END_REF] are very interesting, as they suit well with the idea of benefitting from opportunistic links when possible. Moreover, they show that huge benefits (e.g., email services) can be provided to users by means of asynchronous communications, even if this is at the expense of a potentially (unavoidable) high latency.

Google project Loon4 is another ambitious attempt to connect people in rural and remote areas and bring people back online after disasters thanks to a network of highaltitude balloons. This is promising, although it still remains unclear if such a network infrastructure is durable, since current balloons can only function for a few weeks. In Cape Town (South Africa), Google also participated in The Cape Town TV White Spaces (TVWS) trial 5 , which evaluated the possibility to benefit from unused parts of the frequency bands used for television to enable Internet access [START_REF] Murugesan | Mobile Apps in Africa[END_REF]. For its part, Internet.org promotes low-cost wireless handsets, compression of Web pages, and data caching on the edge of the network, to reduce data transfer. It is complemented by the Alliance for Affordable Internet 6 , a coalition including the public sector and private companies (such as Google and Facebook) as well as civil organizations, which pushes towards progresses in regulation and policy. These different initiatives demonstrate the growing interest, as well as the high difficulty, to integrate LDCs in global IT networks. Obviously, it is still not possible to predict which of those attempts may succeed, and when. Loon project architects believe that this can achieve a commercial success, but confess that it may take a lot of time. In addition, low connectivity is clearly not the ultimate and unique barrier. As already mentioned, the generalization and deployment of e-services in these regions faces many other obstacles: the lack of consistent information systems, security procedures, economic and legal support as well as political commitment, and the difficulty to ensure the maintenance of the system. The specificity of our proposal is to consider the aforementioned obstacles as characteristics of LDCs and to propose a holistic and general data management solution that supports secure data-intensive applications, while taking advantage of existing elements of infrastructure, if any, to improve its own behavior. So, we consider initiatives focusing on communication aspects, like DakNet or project Loon, as complementary to Folk-IS, since any additional means to reduce the network latency and increase connectivity would benefit our vision.

FOLK-IS ARCHITECTURE

As stated in the introduction, the Folk-IS paradigm builds upon the emergence of smart tokens, i.e., highly secure, portable and low-cost storage and computing devices, which may have various form factors (i.e., physical layout) and characteristics. In this section, we consider an abstract Smart Token, to focus on the foundation of Folk-IS and on its mode of operation with no consideration for specific technical choices. We postpone the discussion on real hardware platforms and concrete architectures to Section 5.

Smart Tokens: We consider Smart Tokens embedding at least: (1) enough stable storage to host the complete digital environment of its holder, (2) enough tamper-resistant computing resources to run a server managing the data and enforcing access control rules, and (3) a biometric sensor to authenticate users (e.g., a fingerprint reader, well adapted to illiterate people). Smart Tokens require also input/output capabilities to interact with users and communication facilities (e.g., short-range communications) to exchange messages. To meet the low-cost requirements, a smart token may inherit part of these functionalities from a terminal it connects to, assuming that it does not introduce security breaches.

Folk-enabled Network: since Folk-IS cannot rely on existing communication infrastructures, an ad hoc network of smart tokens is used for transferring messages (i.e., network packets) among smart tokens and from smart tokens to Internet access points. This can be achieved either by using short-range communications between smart tokens (assuming they are equipped with such communication facilities) or through terminals smart tokens connect to (assuming messages are uploaded on the terminal and retrieved by others smart tokens which will next connect to it). So, communications are opportunistic by nature.

Folk-IS Personal Node (Folk-node): it is associated with each individual and refers to the combination of a Smart Token and of the embedded software components required to manage the holder's data, act as a network node, and enforce the security of the whole system. Folk-enabled Information System (Folk-IS): based on the existence of Folk-nodes, we can devise a system implementing the three main functions of an information system as follows:

• Communication management: by carrying and routing data, each Folk-node acts as a node in the Folk-Net.

Assuming that each Folk-node maintains a history of its moves (e.g., by gathering the GPS coordinates of all the devices it connects to), it can forward messages to encountered Folk-nodes (directly, or through terminals) whose moving profile best matches the recipient's location. Such georouting protocol provides a much better resource utilization of the Folk-Net than a basic flooding protocol.

• Data management: each individual centralizes in his Folk-node all his personal data (e.g., medical records, administrative documents, credentials). Each time the holder interacts with a data source (e.g., by physically meeting a data provider, like a doctor, or by receiving a document through the Folk-Net), the application simply inserts these data in a local Folk-node database. From the information system viewpoint, the global database is the "union" of all these local databases. Each Folk-node is assumed to participate in common services, like processing global queries (broadcasted through the Folk-Net) and ensuring data durability (thanks to data replication among Folk-nodes).

• Access control & authentication: each Folk-node controls the access to the data it hosts and strongly authenticates the requesters (and its owner). Performing this control on the user's side is the ultimate solution to increase the holder's confidence, enforce his consent, and minimize the benefit/cost ratio of an attack. Indeed, the complexity of attacking the system is increased by the Smart Token tamper-resistance and by the obligation to be physically in contact with it to attack it.

In parallel, the benefit of the attack is limited to disclosing/corrupting the data of a single individual. Note that the holder himself must authenticate and does not have all the privileges on his own Folk-node (e.g., he cannot tamper his own medical data to prescribe himself new drugs). In addition, messages carried by a Smart Token or replicas from other individuals stored locally are encrypted with keys never available to that Smart Token. Hence, the complete system (data storage and network facilities) progressively deploys itself as Folk-nodes and shared devices are distributed to the participants. Folk-IS is by construction highly-redundant and robust, it does not require any central administration, and its global cost is directly proportional to the scale of the targeted population. As discussed next, some Folk-IS functionalities could be delegated to specific workers (e.g., people renting terminals or acting as postmen) in order to improve the quality of service (QoS) while creating a new local economic model (e.g., like people renting their cell phones in LDCs [START_REF] Brewer | The Case for Technology in Developing Regions[END_REF]). If elements of infrastructure are available, the Folk-IS QoS also improves accordingly, decreasing the network latency by shortening the route to the destination (or to the nearest Internet access point).

Figure 2 illustrates the Folk-IS mode of operation. It shows two rural communities, residents (black icons with letters) and their possible moves (grey icons), a school and a first aid room used by residents from both communities, and an Internet access point. Data exchanges through terminals are represented by dashed lines (e.g., the Folk-node of person A is used from the terminal of nurse N in the infirmary), and short-range data exchanges are represented by pink halos (e.g., between A and B in Community 2). E serves as a netman (i.e., a postman conveying digital messages) and carries data when travelling from place to place (e.g., the school, the infirmary and the Internet access point) thanks to his Folk-node. Different routing paths to transmit a message from A to the Internet are represented, e.g., the path ABTE: person A ! person B ! T (teacher) !E (netman) ! Internet. These paths benefit from the physical mobility of people and their devices. Healthcare scenario: In most LDCs, healthcare is provided by local nurses/doctors working in first aid rooms or intervening in rural communities during drought periods or health programs. They only possess very basic medicines and equipment. Needless to say, they do not benefit from an Electronic Health Records (EHRs) system, which is already highly difficult to organize in developed countries. Even paper-based medical records are too complex to maintain because many people have no identity document to link them to their records and people move according to seasons and drought periods. By using a Folk-node, each patient owns his complete and up-to-date medical folder. Without any Internet connection, a nurse can access the fingerprint-authenticated patient's medical folder, and appends diagnoses and treatment information. She may request medical advice from a distant clinic, by transmitting documents (e.g., a picture of the patient's injury) from the patient's Folk-node through the Folk-Net. She can notify the patient a few days later, still through the Folk-Net, in case a serious problem has been detected. In this case, the same architecture could also be used to detect and anticipate epidemics to better limit and fight them. Global queries can also be broadcasted through the Folk-Net to conduct epidemiological studies or maintain health indicators on populations unreachable so far. Hence, each Folk-node acts as a smart Personally Controlled Electronic Health Record (PCEHR).

Cultural heritage: Benefiting from the distributed and traveling Folk-IS architecture, new practices could be put in place to produce and share pieces of cultural heritage, within communities or towards the outside world through virtual museums. Thus, with the help of cultural organizations, users able to produce pieces of a cultural heritage, related to traditional stories, songs, beliefs or cultural events, could be identified and equipped with Folknodes. Other users able to describe or translate such productions could also be equipped, and share/publish the enriched cultural content to virtual museum. The exact contribution of each actor (e.g., content producer, descriptors, translators, etc.) could be recorded, watermarked and certified by his tamper-resistant Folknode. This may generate a new economic model where actors could be paid according to their contributions.

Generalization: Many usual scenarios can be transposed to rural communities thanks to Folk-IS, provided that they accommodate high-latency data exchanges: scholar folders for children, e-administration procedures (e.g., drought warnings, recording births and deaths), personal data applications (e.g., email, social or networking services), etc. This may also generate a new economic model where every actor could be paid according to his contribution, as exemplified in the cultural heritage scenario. It could also be the case for people playing the role of a netman, who could be paid according to the volume of transported data, the amount of population touched and the distance covered.

CONCRETE FOLK-IS INSTANCES

Let us now go from abstract smart tokens to the concrete hardware platforms. Given our target, an essential element in the design of the Folk-node's hardware is its cost, since it determines alone the overall cost of the Folk-IS solution.

To decrease this cost, we study whether some of the Folknode's hardware resources can be shared while minimizing the impact on the Folk-node's functionalities. To this end, we distinguish between Folk-node hardware platforms associated with individuals and shared devices which are either made publicly available in specific places or owned by local workers (e.g., nurses, teachers, administration officers, merchants). In the following, we first describe each Folk-node's resource arguing the pros and cons of sharing it. Then we examine the design of shared devices. Finally, we consider the whole Folk-IS architecture and discuss some deployment scenarios.

Folk-IS Hardware Platforms

Resources in Folk-nodes

As mentioned in Section 3, Folk-nodes are expected to embed storage, security, communication, location, and I/O resources.

Storage resources. Flash memory is undoubtedly the most adequate storage medium, thanks to its robustness, compact form factor, low cost, and low energy consumption characteristics. The main storage resources must be located on the Folk-node itself for obvious availability reasons (e.g., the holder's medical folder must be accessible anytime and anywhere when carried by the holder) and then cannot be shared. The storage capacity must afford the storage of all the holder's data as well as the persistent data required by common services (e.g., durability data, network packets, etc.).

Security resources.

Secure microcontrollers (SMCUs) [START_REF] Bursky | Secure Microcontrollers Keep Data Safe[END_REF] can provide tangible security guarantees, and are today available at very low cost, in a small form factor (e.g., a SIM card), generally combined with an external (unsecure) flash chip. Existing SMCUs typically embed a relatively powerful processor (e.g., clocked at about 50 MHz), a cryptographic co-processor, and an internal secure stable storage (around 1 MB) to store the embedded code (e.g., the OS, a data management engine, the authentication mechanism, etc.) and sensitive metadata (e.g., cryptographic material used to protect the holder's data). Since we cannot assume that each user has an electronic identity (this would require certificates and a PKI -Public Key Infrastructure-, which contradicts our infrastructureless assumption), we consider the use of a biometric sensor to prove the identity of the user. Biometric sensors (e.g., fingerprint readers) seem well adapted to illiterate users since this avoid remembering and typing a password or PIN code. At the personalization step (i.e., before the first use), the user's fingerprint is stored inside the SMCU's secure memory and it is then checked at each access.

SMCUs and fingerprint readers are at the heart of the security system of Folk-IS. They cannot be disassociated from the Folk-nodes (i.e., associated with the terminals the Folk-nodes connect with) without introducing the risk of class-breaking attacks (i.e., breaking a single-shared terminal would enable access to the sensitive data of all the Folk-nodes sharing that terminal). The privacy and security requirement is thus fulfilled, due to a combination of factors: (1) the guarantee of an implicit user's consent (no access to the data without the holder's fingerprint check) and of a strong authentication of local workers; (2) the obligation to be physically in contact with the device to attack it; (3) the tamper-resistance of the Folk-node's processing and storage units, which makes hardware and side-channel attacks highly difficult; (4) the certification of the embedded software platform, which makes software attacks also highly difficult; and (5) the impossibility, even for the Folk-node's holder, to directly access the data stored locally or involved into local computations (he must authenticate and can only get data according to his privileges).

Communication resources.

To enable the human network described in Section 3, Folk-nodes need a means to communicate together. This could be achieved either by using short-range communications or by physically plugging Folk-nodes in shared devices: messages can be temporarily stored encrypted on the shared device and delivered to Folk-nodes that will be plugged later. The advantage of enabling Folk-nodes with wireless capabilities is that messages can be exchanged without help from shared devices. However, wireless communications need energy, thus imposing the need of a battery and some mechanism to charge it (e.g., energy harvesting technologies). Solutions with a limited amount of energy can also be exploited to improve the connectivity of the Folk-net, as discussed in Section 6.2.

Location resources.

The network routing will be done based on the geographical location of the devices, raising the need to obtain at least an approximate location of Folknodes. Different alternatives could avoid embedding a costly positioning mechanism in each Folk-node. For example, the location information can be deduced from interactions with a small subset of localized Folk-nodes, shared devices, or fixed nodes. The user's home address can also be stored on each Folk-node at the personalization step, giving approximate static information about its location.

Input/Output (I/O) resources. Classical I/O resources must be available to enable user interactions with a Folk-node. A screen, a keyboard (or a touch screen), a microphone and a speaker are obvious I/O elements. They have however different form-factor and cost/energy requirements. Fortunately, most user interactions will happen with local workers and thus can make use of their own device's I/O resources. In addition, illiterate users will probably underuse the keyboard or the screen. Such I/O resources can thus be located on shared devices without a significant impact on the platform usability, while keeping a speaker and microphone on the Folk-node would allow basic users' interactions autonomously.

Energy considerations and concrete Folknodes

In an infrastructure-less context, the electrical power network is limited and leads to consider energy as a particularly scarce resource. To this respect, let us first consider two extreme designs for the Folk-nodes: passive and active ones (see the top of Figure 3).

The passive Folk-node embeds only mandatory resources (i.e., related to storage and security) and has no internal battery, and thus cannot be used without a shared device. It achieves the lowest cost at the expense of needing a shared device to be used. The intrinsic characteristics of a passive Folk-node are its low cost and robustness, inherited from its simplicity. It is very similar to a smart token product, provided by Gemalto, that we used in a field experiment [START_REF] Allard | Trustworthiness of Pervasive Healthcare Folders[END_REF][START_REF] Anciaux | Trusted Cells: A Sea Change for Personal Data Services[END_REF][START_REF] Anciaux | Pluggable Personal Data Servers[END_REF]. This kind of smart token is available for a few dollars, in a SIM card form factor (plugged in a USB key casing), and simply needs to be extended with a fingerprint reader, in a way similar to traditional secure USB keys.

The active Folk-node is more complex, since it embeds a battery and the required means to charge it and power a wireless communication element (Bluetooth, led-light communications, ...). It is also equipped with I/O resources to allow basic users' interactions autonomously. Typically, we keep a speaker and microphone, given their small form factor, robustness and low-cost/low-energy profiles. Thus, active Folk-nodes provide certain functionalities to endusers even without being connected to a shared terminal, and they can communicate (typically, they can exchange messages wirelessly with surrounding active folk-nodes).

Capitalizing on various energy harvesting technologies (Piezo-electric, solar, etc.), other intermediate designs would make sense, leading to Folk-nodes being active intermittently, then called partially active Folk-nodes. For example, a Folk-node could be endowed with piezoelectric energy harvesting technologies and could become active at the will of its owner, a mechanical interaction with the equipment being needed to power the device for short durations.

Shared Devices

Any hardware resource mentioned in the previous section and not present in Folk-nodes should be available in shared devices, that is: (1) for the passive Folk-nodes, all the I/O resources (screen, keyboard, speaker and microphone), some flash memory (for durability and communication purposes), and location mechanisms (for helping routing messages); (2) for the active Folk-nodes, a keyboard, a screen, and a location mechanism.

The bottom of Figure 3 shows three possible instances of shared devices. The specific Folk-IS device (on the left) is designed especially for the Folk-IS architecture. The idea is to increase the robustness of the deployed solution by providing a closed architecture, i.e., a device with no possibility to install any software or hardware components different from those developed and validated by Folk-IS (note that this does not mean proprietary hardware or software). An alternative is to make use of the devices that local workers potentially already own (e.g., a smartphone or a computer, as shown on the right of Figure 3) in order to further reduce the overall cost of the Folk-IS architecture. Indeed, the required shared resources are generally present in these devices. If a device misses some resource (e.g., it has no location facilities, or has a small available storage), then the service will be locally degraded, but this does not hinder the global architecture (typically, the estimated location will be more imprecise, the durability will be provided elsewhere, etc.).

Concrete Architectures and Deployment Scenarios

Based on the discussion above, different combinations of Folk-nodes / shared devices and different deployment scenarios can be envisioned. The initial deployment of Folk-IS should be based on the most simple and robust combination, in order to minimize the risks of a too-open or too-complex architecture. Thus, we first consider the combination passive Folk-nodes / specific Folk-IS shared device, whose main advantages are robustness and low cost (a few dollars for the Folk-node, less than US$100 for the shared device, with the cost of shared devices having a small impact on the cost of the overall solution).

Then, more expensive partially active or active Folk-nodes (of a few tens of dollars) could be progressively acquired and distributed to unequipped individuals requiring a lower latency of communications or wishing to access their Folknodes without the need of a shared device (e.g., by adding a microphone or speaker).

An orthogonal direction for enhancing the initial deployment is to open the Folk-IS solution to existing devices potentially owned by users or local workers. This means allowing Folk-nodes to connect to a larger set of (hardware adaptors may be needed to enable physical connections) and to upload applications (retrieved through the Folk-Net) to these devices. Such open architecture is more complex due to device heterogeneity but it brings many benefits: (1) it lowers the overall cost of the Folk-IS architecture; [START_REF] Allard | Trustworthiness of Pervasive Healthcare Folders[END_REF] it increases the number of potential terminals, thereby increasing data availability and reducing network latency; and (3) it allows third parties to develop interesting user-centric applications, thus increasing the benefit to the users. These two directions (i.e., more active Folk-nodes and open Folk-IS) are not exclusive. We believe that a final Folk-IS architecture will indeed include passive Folk-nodes, active ones, specific Folk-IS shared devices, and existing devices, their proportion being highly dependent on the context.

DATABASES CHALLENGES

Several challenges of Folk-IS are at the crossroad of Computer Science, Economics, and Social Science. A first one is to formalize and quantify the impact of different Folk-IS configurations on e-inclusion, and more generally on social and economic progresses in LDCs. A second important challenge is linked to the study of specific human-computer interactions, made complex by the fact that some users might be illiterate and lack training. This section however focuses on database related challenges.

Co-design of the Embedded Data Management Engine

A primary role of a Folk-node is to ensure secure storage and sharing of all data forming the holder's digital environment: user authentication, secure data storage, query evaluation and access control enforcement. The fingerprint reader enables authenticating the requester (e.g., a nurse) at each access, so that privileges can be properly associated with him/her in order to protect data confidentiality and integrity. In a data management system, fine-grained privileges granted to subjects on objects are usually identified by expressions (i.e., queries) over the data. These queries determine the information that can be accessed by the subject (other data remain hidden). Hence, answering accurately the Folk-IS privacy and security requirement leads to embed a data management engine within the Folknode, in charge of evaluating queries over the data, checking the integrity of any data involved in the computation, and delivering the result to the grantee subject. When considering a relational database, the queries are formulated using the relational algebra (involving selection, projection, joins and aggregation operators). Whenever documents are managed, queries are usually defined using expressions over tags/labels associated to the documents.

Evaluating queries within a Folk-node, even expressed using simple expressions over tags, is very challenging due to the strong and conflicting inherent hardware constraints of smart tokens. Whatever their exact characteristics, low cost and low energy, embedded devices are always endowed with: (1) a small amount of RAM (because of its low density and its high relative impact on the overall cost of the device); and (2) NAND flash memory (the most adopted persistent memory for embedded devices, due to its high density and high robustness), which exhibits bad performance for random writes. In addition, in the context of the Folk-node, the raw data should be protected using cryptographic features to ensure the confidentiality and integrity of the stored data. These constraints lead to contradictory objectives: executing queries with acceptable performance with a tiny RAM entails massively indexing the embedded database in NAND Flash, while index updates generate fine-grained random writes, and then unacceptable performance due to NAND flash write costs and cryptographic overhead.

These statements make any state-of-the-art solution impractical, and call for the design of brand-new data management techniques. Existing embedded DBMSs (e.g., SQLite, BerkeleyDB) and light versions of popular DBMSs (e.g., DB2 Everyplace, Oracle Database Mobile Server) target devices far more powerful than smart tokens (like smart phones or tablets), and do not tackle the abovementioned constraints. Most of the recent proposals addressing the problem of storage and indexing in Flash, like [START_REF] Agrawal | Lazy-adaptive tree: An optimized index structure for flash devices[END_REF][START_REF] Li | Tree indexing on solid state drives[END_REF], adapt the traditional B+-Tree to Flash memory by relying on a Flash-resident log to delay the index updates. When the log is large enough, the updates are committed into the B+-Tree in batch mode, to amortize the Flash write cost. The log must be indexed in RAM to ensure performance. To amortize the write cost by large factors, the log is seldom committed, to a higher RAM consumption. Conversely, limiting the RAM size means increasing the commit frequency, thus generating more random writes. Under strong RAM limitations, the commit frequency becomes de facto very high and the gain on random writes vanishes. Flash-aware implementations of key-value stores [START_REF] Vo | LogBase: A scalable log-structured database system in the cloud[END_REF][START_REF] Lim | SILT: A memory-efficient, high-performance key-value store[END_REF] also use a log structure in Flash to store key-value pairs and exploit sequential writes. But again, an index must be maintained in RAM, with a relatively large size (~1B per key-value pair) to obtain acceptable performances.

Recent proposals more specifically handle the smart token constraints. Microsearch [START_REF] Tan | Microsearch: A search engine for embedded devices used in pervasive computing[END_REF] is a search engine designed for sensor nodes, answering full text search queries in a pure pipeline fashion, thus fulfilling the tiny RAM constraint. MiloDB [START_REF] Anciaux | MILo-DB: A personal, secure and portable database machine[END_REF] is a database machine for future generations of SIM cards with large storage capacities (a NAND Flash chip is superposed to the secure microcontroller of the SIM card). The database is organized into sequential Log Containers in NAND Flash, supports a massively indexed database while avoiding random writes by definition, and is able to compute SQL star join queries within the microcontroller. These proposals demonstrate the growing interest of storing and querying large amounts of data in smart tokens, but remain restricted to particular data models and specific types of smart tokens.

In Folk-IS, a much broader scope in terms of data models and hardware components have to be investigated to codesign and implement the best storage, indexing and query engine considering a triple objective: reducing the overall cost of the device, reducing its energy consumption, and offering a high level of flexibility. To this end, other hardware choices will have to be envisioned. For example, a combination of a very low cost secure (tamper-resistant) microcontroller coupled with a regular microcontroller could be preferred. It would provide the expected level of security, would be more flexible, and would consume less energy (regular microcontrollers have a larger RAM size with respect to tamper-resistant ones, which increases performance and thus reduces energy consumption). Regarding persistent memory (NAND Flash), a micro-SD card would undoubtedly offer better flexibility and lower cost than a raw Flash die: the card could be replaced at will by a cheaper, larger or more efficient one, and it could also be kept when replacing a deficient device. Supporting micro-SD cards has a strong impact on the software design since it leads to access the NAND Flash through a Flash Translation Layer (FTL). An FTL is a software layer, proprietary, and potentially different for each micro-SD card, leading to different behaviors in terms of access time, read/write performance ratios, number of sequential data files that can be written sequentially, etc. Data management techniques designed for such a variable environment must be adaptive: the frequency of index refreshment would have to adapt to the performance of the micro-SD card, as well as many parameters regarding the storage and indexing structures.

Towards Folk-Net Routing and Mobility Prediction

We present here the global concept the communication protocols should enable in the Folk-IS paradigm. We also describe the directions we will investigate to achieve this based on existing approaches. The communication should be enabled either directly between active Folk-nodes (i.e., both equipped with communication facilities) or indirectly through a shared device (e.g., encrypted messages are exchanged as passive Folk-nodes successively connect to the same device, acting as a relay at a clinic, a school, etc.). Moreover, some humans may play the role of "netmen", gathering data to relay ("letters") and physically carrying them to other shared devices (or "intermediate delivery points") for further distribution. Folk-Net can be homogeneous (i.e., exclusively composed of active or passive Folk-nodes) or hybrid, in which case network latency and throughput will depend on the proportion of each type of node and of netmen. Folk-Net will thus rely on opportunistic communications [START_REF] Huang | A Survey of Opportunistic Networks[END_REF] by nature, which poses a set of challenges in terms of routing, mobility prediction and energy consumption.

Routing protocols

The choice of the best candidate(s) to carry the encrypted data towards their destination is a primary concern to avoid flooding the human network. Many routing protocols have been proposed for wireless networks. OLSR and AODV, designed for MANETs (Mobile Ad hoc Networks) [START_REF] Kiess | A survey on realworld implementations of mobile ad-hoc networks[END_REF], are disqualified in the Folk-IS context due to the great amount of messages they require. ZigBee cannot be considered either. Indeed, it relies on a routing tree and thus is not reliable against node mobility. Geographic routing protocols are more interesting candidates as they do not need to maintain routing tables and work nearly stateless [START_REF] Rührup | Theory and Practice of Geographic Routing[END_REF]. However, they rely on the following assumptions: (1) the location of the packets' recipient is known, and (2) every node capable of routing information knows its own position and trajectory. Both assumptions cannot be assumed in the Folk-Net context, motivating new research efforts.

Folk-IS also shares some similarities with VANETs (Vehicular Ad Hoc Networks) [START_REF] Hartenstein | Vehicular Applications and Inter-Networking Technologies[END_REF]. Whereas some features differ significantly (e.g., the underlying communication standard, the communication range, the speed and power of nodes, etc.), both environments share the same lack of infrastructure and dynamic topology. Hence, we believe that protocols designed in the VANET context, like carryand-forward [START_REF] Fenu | Strategies to Carry and Forward Packets in VANET[END_REF] or content-based dissemination [START_REF] Cenerario | A Content-Based Dissemination Protocol for VANETs: Exploiting the Encounter Probability[END_REF], could be adapted to Folk-IS. Carry-and-forward protocols are well suited to sparse networks. They exploit some nodes as "data mules" to carry the information and deliver it to other nodes encountered along their trip. On the contrary, content-based dissemination protocols limit the number of nodes relaying the message in dense networks.

So, in the Folk-IS context, carry-and-forward protocols could be investigated to deliver messages (e.g., a query result), whereas content-based dissemination could be considered to efficiently disseminate a query to the nodes holding potential results.

Mobility prediction and profiling

As commented in Section 5.1.1, no exact GPS location can be assumed for the Folk-IS nodes. Instead, their location must be approximated from interactions with a small subset of localized Folk-nodes, either shared devices or fixed nodes. Besides, active Folk-nodes can also compute an approximate location based on the position of their neighbors using techniques based on RSSI (Received Signal Strength Indicator).

Approximate locations can be combined with mobility prediction techniques to predict the future movements of Folk-nodes. Many mobility prediction techniques only rely on the history of the user's mobility patterns and thus are insensitive to the changes of the user behavior. Other techniques are based on both the history of the mobility patterns and formal models (e.g., [START_REF] Liu | A Class of Mobile Motion Prediction Algorithms for Wireless Mobile Computing and Communication[END_REF]). In [START_REF] Barth | Mobility Prediction Using Mobile User Profiles[END_REF][START_REF] Barth | Combining Local and Global Profiles for Mobility Prediction in LTE[END_REF], a new approach is investigated combining the notions of local and global profiles. While local profiles capture the recurrent behaviors of each user (like going to the office every day at the same hour and using, more likely, the same paths), global profiles capture a set of frequently-followed paths by a certain percentage of users (main roads, trains, etc.). This approach achieves a much better prediction success rate and could lead to great delivery and energy performance in Folk-IS georouting. Local profiles could be maintained in each Folk-IS node for privacy concern while global profiles could be anonymized and hosted in shared devices during a certain period of time.

Routing with mobility prediction

New routing protocols mixing geolocation approximation, mobility prediction strategies and social interactions (e.g., [START_REF] Gao | Multidimensional Routing Protocol in Human-Associated Delay-Tolerant Networks[END_REF][START_REF] Wang | Analysis of a Hypercube-Based Social Feature Multipath Routing in Delay Tolerant Networks[END_REF]) definitely deserve to be studied to select the best "data mules" for each message. In relation to this topic, it is worth mentioning that the problem of detecting and tracking "familiar strangers" (unknown people that one may frequently encounter during his/her everyday activities) has attracted the attention of research, due to the interest in understanding human behavior and diffusion processes [START_REF] Suna | Understanding metropolitan patterns of daily encounters[END_REF]. This emphasizes the interest of considering the social behavior in the design of opportunistic routing protocols. As another example, [START_REF] Kang | Leveraging Social Networks for P2P Content-Based File Sharing in Disconnected MANETs[END_REF] distinguishes between stable nodes that have frequent contacts with others within the same community (chosen as community coordinators for searching information within the community) and highly mobile nodes that frequently visit other communities (chosen as community ambassadors for searching information in other communities). These concepts could be applied similarly in the context of Folk-IS.

Energy saving

Active Folk-nodes having a limited autonomy in terms of energy must detect neighbors at low cost and form an ad hoc network whose topology and density may change over time (e.g., the network may be quite stable and dense in a village but quite sparse elsewhere, a dynamic neighborhood may become stable when owners of Folk-nodes enter the same bus, etc.). Every task should thus integrate energy consumption considerations. This could be done through transmission range adjustment when communicating (a node can increase/decrease its transmission power sending data more or less far and reaching more or less nodes) and set up of duty cycling (deciding when to turn off/on the radio to save energy). Range adjustment allows the reduction of the energy spent for sending (the message is sent to a closer node at a lower power) and for overhearing (it will reach less nodes), and generates less interference. It has to be included in the georouting protocol (like in [START_REF] Mitton | Guaranteed Delivery in k-Anycast Routing in Multi-Sink Wireless Networks ICST Mobile Communications and Applications[END_REF]). The duty cycle is based on the node activity and its neighborhood. If a node does not need to communicate and there are enough active nodes in its neighborhood to ensure the relay of other nodes' messages, it can simply sleep and save energy. This operation can also be enhanced through the use of prediction models.

Application, Data Model and Access Control Deployment

As discussed in Section 4, Folk-IS enables many important applications, like email services, healthcare, and eadministration, some of them novel by their purpose (e.g., sharing pieces of a cultural heritage) or by their target (e.g., epidemiological studies on populations unreachable so far). The infrastructure-less context introduces new challenges with respect to application deployment, unified data modeling, identity verification, access control, and user's consent. Typically, data standardization, central application stores or central authorities identifying people, delivering certificates and enforcing access control rules on central servers, cannot be assumed. Conversely, a salient feature of Folk-IS is the ability to push the control at the edge of the network, that is to say (1) within each tamper-resistant Smart Token, and (2) through face-to-face interactions between users, implementing a de-facto user's consent. This may enable the reestablishment of local spheres of trust. For example, NGOs could produce applications, data models, home-made identification information, access control policies, and push them at the Folk-node level through Folk-Net. Specific workers could also be involved in the application installation and maintenance phases. This paves the way to a semi-decentralized way of managing and deploying applications, each Folk-node guaranteeing that (i) data produced by a given organization will not leak outside that organization, and (ii) the data owners' privacy is always respected.

Evaluation of Global Queries on a Population of Folk-nodes

Traditional techniques used to process queries in distributed databases or in peer-to-peer networks are not suitable, as they usually assume a good knowledge about the location of the data items in the network and do not consider the mobility of nodes. Here the data items will be dynamically distributed over a network of nodes that may be accessible or not at a certain moment, and the carrier of a replica of a data item may change at any time. Moreover, we cannot assume that all the data items relevant to a given query will always be available and retrievable in a reasonable time period. So, we should adopt the openworld assumption, admit the possibility of approximate answers, decide how to identify the relevant data sources without overloading the network (e.g., based on spatial conditions), how to route queries and results to their recipients (while preserving autonomy) using geographic routing and the physical mobility of nodes, and how to determine when a query and its associated routing tasks have to be finished. Moreover, new types of queries could be of interest in this context, requiring new query processing techniques; for example, reachability queries [START_REF] Shirani-Mehr | Efficient Reachability Query Evaluation in Large Spatiotemporal Contact Datasets[END_REF] could be used to study the possibility of propagation of a disease by analyzing past trajectories.

Structure and Calibration of the Folk-IS Architecture

Folk-IS is built on a large number of highly-secure but seldom-available Folk-nodes (active or passive) on the one side, and on less secure but more accessible and powerful shared devices on the other side. This unusual asymmetric architecture requires deeply rethinking the overall organization of an information system. This means distributing software resources on the hardware elements of the architecture, such that local and global applications can run and provide results with acceptable performance, security and resiliency. This also means associating different responsibilities to different devices (e.g., supernodes), associating specific roles to humans (e.g., netmen to reduce latency), and designing new distributed protocols to implement global functionalities like query evaluation or data durability. For the latter, data replication is required because Folk-nodes may be lost, stolen, broken, etc. Data could be replicated based on the mobility profiles of the users. Confidentiality of replicas can be achieved through encryption, leading to the problem of choosing the most adequate set of Folk-nodes to hold a copy of the keys or of key shares (e.g., based on trust or similar mobility profiles). Finally, new simulation models are needed to calibrate IT resources according to the target applications and the local habits of residents. The objective is to determine suitable network topologies (given a certain density of Folk-nodes, communication frequency, etc.) with viable incremental deployments. Those simulation models will also help quantifying the expected gain in terms of social and economic sustainability, which is key for their adoption in the long term.

CONCLUSION

As mentioned in [START_REF] Brewer | The Case for Technology in Developing Regions[END_REF], time has come for research works, not only commercial initiatives, addressing the expectations of 80% of the population living outside developed countries. The Folk-enabled Information System (Folk-IS) paradigm combines low-cost secure devices, embedded software components and opportunistic communications, to meet fundamental requirements of LDCs. The promise of the solution is to fulfill the requirements stated in the introduction:

• Privacy protection: Folk-IS inherits its security and privacy protection from the tamper-resistance of each token and from the delegation of the access control and authentication tasks to each Folk-node, at the user's side. Moreover, any user must authenticate to the Folknode, which securely records any performed action in an audit log, making the complete system accountable. The holder himself may be authenticated by the Folknode, and may not have all the privileges on his own records.

• Immediate personal benefit: Folk-IS makes the Folknode of each individual play the role of a passport for a wide range of critical applications: healthcare, eadministration, education, market rates for farmers, emails, etc. In parallel, governments and NGOs benefit from a new channel to pull/push information from/towards communities previously unreachable.

• Self-sufficiency: Folk-IS is infrastructure-less by construction. The complete system (data storage and network facilities) progressively and automatically deploys itself as Folk-nodes are distributed to the participants, with the ability to benefit from future infrastructure improvements.

• Very low deployment cost: Folk-nodes are hosted in low-cost smart tokens and the global cost of the system is directly proportional to the scale of the targeted population. In addition Folk-IS is by construction a highly-redundant and robust system that does not require any central administration. The maintenance and performance improvement of the system can be a source of empowerment with new local jobs (e.g., people renting terminals or acting as postmen), crucial to make the solution sustainable.

Hence, we expect that this paper could pave the way to exciting future works for our research community as well as to fruitful experiments in the field as soon as the major challenges are tackled.

Figure 2 .

 2 Figure 2. Folk-IS: mode of operation

Figure 3 .

 3 Figure 3. Folk-IS architecture elements

http://a4ai.org/press-centre/what-our-supporters-say/

http://nextdrop.org/

http://www.pacinst.org/reports/mwash

http://www.google.es/loon/

http://newweb.tenet.ac.za/tvws/.

http://a4ai.org/

ACKNOWLEDGMENTS

We warmly thank Léo Dayan, scientific director of APREIS NGO and of the Nomadic World University for Sustainable Development, as well as Pascale Pollack, director of E-NEXUS NGO, for precious discussions and feedback on the requirements of IT solutions for LDCs.


Riccardo Petrolo

Valeria Loscrì

Nathalie Mitton

Towards a Cloud of Things Smart City

come