Search

In this paper, we study uncontended complexity of anonymous k-set agreement algorithms, counting the number of memory locations used and the number of memory updates performed in operations that encounter no contention. We assume that in contention-free executions of a k-set agreement algorithm, only “fast” read and write operations are performed, and more expensive synchronization primitives, such as CAS, are only used when contention is detected. We call such concurrent implementations interval-solo-fast and derive the first nontrivial tight bounds on space complexity of anonymous interval-solo-fast k-set agreement.

Anonymous Dynamic Networks is a harsh computational environment due to changing topology and lack of identifiers. Topology changes are well motivated by mobility and unreliable communication environments of present networks. With respect to node identifiers, in future massive networks it may be necessary or at least convenient to avoid them to facilitate mass production.

Ensuring causal consistency in a Distributed Shared Memory (DSM) means all operations executed at each process will be compliant to a causality order relation. This paper first introduces an optimality criterion for a protocol P, based on a complete replication of variables at each process and propagation of write updates, that enforces causal consistency. This criterion measures the capability of a protocol to update the local copy as soon as possible while respecting causal consistency. Then we present an optimal protocol built on top of a reliable broadcast communication primitive and we show how previous protocols based on complete replication presented in the literature are not optimal. Interestingly, we prove that the optimal protocol embeds a system of vector clocks which captures the read/write semantics of a causal memory. From an operational point of view, an optimal protocol strongly reduces its message buffer overhead. Simulation studies show that the optimal protocol roughly buffers a number of messages of one order of magnitude lower than non-optimal ones based on the same communication primitive.

A comparison between the biotic signal recorded in the Tethyan Cenomanian black shales and in the Mediterranean Pleistocene sapropels is proposed here. To this end the Antruiles section (northeastern Dolomites, Italy) has been investigated as a reference section for the Cenomanian black shales. The data obtained, based on calcareous nannofossils and foraminifera, have been compared to those from a core in the Mediterranean Sea containing a complete succession of Late Pleistocene–Holocene sapropels. Our study suggests that deposition of black shales, like sapropels, occurred when the water column was stratified, as implied by increased abundance of the Cenomanian deeper-dwellers Rotalipora cushmani and R. greenhornensis. The superficial/subsuperficial opportunist form Heterohelix reussi, which strongly increases in numbers within the black shales, could be analogous to the modern surface-dweller Globigerinoides ruber, which is abundant in Late Pleistocene–Holocene Mediterranean sapropels. The peaks of G. ruber can be related to decreased salinity in surface water, thus the increase of H. reussi could also be related to a freshwater superficial layer. We hypothesise also that an increase in abundance of Watznaueria barnesae reflects conditions of superficial low salinity. In black shales increases in abundance of Dicarinella algeriana and Praeglobotruncana gibba, by analogy to modern Neogloboquadrina dutertrei, could reflect availability of food restricted to subsuperficial waters. However, a Cretaceus equivalent of the Pleistocene nannoplankton form Florisphaera profunda, which proliferates within the Deep Chlorophyll Maximum, is not observed. In addition, the abundance of H. reussi indicates a well-expanded oxygen minimum zone, although less in extent than in Pleistocene sapropels, as shown by the occurrence within the Cenomanian black shales of a benthic fauna, even though reduced in size and impoverished. Spectral analysis applied to calcareous nannofossils identifies close relations with the Milankovitch precession and eccentricity cycles in both the black shales and the sapropels.

In this paper we study efficient implementations for deterministic abortable objects. Deterministic abortable objects behave like ordinary objects when accessed sequentially, but they may return a special response abort to indicate that the operation failed (and did not take effect) when there is contention.

The topic of this paper is the study of Information Dissemination in Mobile Ad-hoc Networks by means of deterministic protocols. We characterize the connectivity resulting from the movement, from failures and from the fact that nodes may join the computation at different times with two values, α and β, so that, within α time slots, some node that has the information must be connected to some node without it for at least β time slots. The protocols studied are classified into three classes: oblivious (the transmission schedule of a node is only a function of its ID), quasi-oblivious (the transmission schedule may also depend on a global time), and adaptive. The main contribution of this work concerns negative results. Contrasting the lower and upper bounds derived, interesting complexity gaps among protocolclasses are observed. More precisely, in order to guarantee any progress towards solving the problem, it is shown that β must be at least n − 1 in general, but that β ∈ Ω(n 2/ log n) if an oblivious protocol is used. Since quasi-oblivious protocols can guarantee progress with β ∈ O(n), this represents a significant gap, almost linear in β, between oblivious and quasi-oblivious protocols. Regardingthe time to complete the dissemination, a lower bound of Ω(nα + n 3/ log n) is proved for oblivious protocols, which is tight up to a polylogarithmic factor because a constructive O(nα + n 3 log n) upper bound exists for the same class. It is also proved that adaptive protocols require Ω(nα + n 2), which is optimal given that a matching upper bound can be proved for quasi-oblivious protocols. These results show that the gap in time complexity between oblivious and quasioblivious, and hence adaptive, protocols is almost linear. This gap is what we call the profit of global synchrony, since it represents the gain the network obtains from global synchrony with respect to not having it. TRUE pub

In this paper the problem of information dissemination in Mobile Ad-hoc Networks (MANETs) is studied. The problem is to disseminate a piece of information, initially held by a distinguished source node, to all nodes in a target set. We assume a weak set of restrictions on the mobility of nodes, parameterized by α, the disconnection time, and β, the link stability time, such that the MANETs considered are connected enough for dissemination. Such a connectivity model generalizes previous models in that we assume much less connectivity, or make explicit the assumptions in previous papers. In MANETs, nodes are embedded in the plane and can move with bounded speed. Communication between nodes occurs over a collisionprone single channel. We show upper and lower bounds for different types of randomized protocols, parameterized by α and β. This problem has been extensively studied in static networks and for deterministic protocols. We show tight bounds on the randomized complexity of information dissemination in MANETs, for reasonable choices of α and β. We show that randomization reduces the time complexity of the problem by a logarithmic or linear factor, depending on the class of randomized protocol considered. TRUE pub

International audience; In this paper, we investigate the exclusive perpetual exploration of grid shaped networks using anonymous, oblivious and fully asynchronous robots. Our results hold for robots without sense of direction (i.e. they do not agree on a common North, nor do they agree on a common left and right ; furthermore, the "North" and "left" of each robot is decided by an adversary that schedules robots for execution, and may change between invocations of particular robots). We focus on the minimal number of robots that are necessary and sufficient to solve the problem in general grids. In more details, we prove that three deterministic robots are necessary and sufficient, provided that the size of the grid is n ×m with 3 ≤ n ≤ m or n = 2 and m ≥ 4. Perhaps surprisingly, and unlike results for the exploration with stop problem (where grids are "easier" to explore and stop than rings with respect to the number of robots), exclusive perpetual exploration requires as many robots in the ring as in the grid. Furthermore, we propose a classification of configurations such that the space of configurations to be checked is drastically reduced. This pre-processing lays the bases for the automated verification of our algorithm for general grids as it permits to avoid combinatorial explosion.

In the context of Mobile Ad-hoc Networks (MANET), we study the problem of disseminating a piece of information, initially held by a source node, to some subset of nodes. We use a model of MANETs that is well suited for dynamic networks and opportunistic communication. We assume that network nodes are placed in a plane where they can move with bounded speed; they may start, crash and recover at different times, and they communicate in a collision-prone single channel. In this setup informed and uninformed nodes may be disconnected for some time, but eventually some informed-uninformed pair must be connected long enough to communicate. We show negative and positive results for different types of randomized protocols, and we contrast them with our previous deterministic results.

International audience; In this paper, we study the exclusive perpetual exploration problem with mobile anonymous and oblivious robots in a discrete space. Our results hold for the most generic settings: robots are asynchronous and are not given any sense of direction, so the left and right sense (i.e. chirality) is decided by the adversary that schedules robots for execution, and may change between invocations of a particular robots (as robots are oblivious). We investigate both the minimal and the maximal number of robots that are necessary and sufficient to solve the exclusive perpetual exploration problem. On the minimal side, we prove that three deterministic robots are necessary and sufficient, provided that the size n of the ring is at least 10, and show that no protocol with three robots can exclusively perpetually explore a ring of size less than 10. On the maximal side, we prove that k = n − 5 robots are necessary and sufficient to exclusively perpetually explore a ring of size n when n is co-prime with k.

Graph exploration by robots. The graph exploration problem consists in making one or several mobile entities visit each vertex of a connected graph. The mobile entities are sometimes called agents or robots (in the following we use the word "robot"). The exploration is perpetual if the robots have to revisit forever each vertex of the graph. Perpetual exploration is required when robots have to move to gather continuously evolving information or to look for dynamic resources (resources whose location changes with time). If nodes and edges have unique labels, the exploration is relatively easy to achieve.

Given an arbitrary partial anonymous grid (a finite grid with possibly missing vertices or edges), this paper focuses on the exploration of such a grid by a set of mobile anonymous agents (called robots). Assuming that the robots can move synchronously, but cannot communicate with each other, the aim is to design an algorithm executed by each robot that allows, as many robots as possible (let k be this maximal number), to visit infinitely often all the vertices of the grid, in such a way that no vertex hosts more than one robot at a time, and each edge is traversed by at most one robot at a time. The paper addresses this problem by considering a central parameter, denoted ρ , that captures the view of each robot. More precisely, it is assumed that each robot sees the part of the grid (and its current occupation by other robots, if any) centered at the vertex it currently occupies and delimited by the radius ρ . Based on such a radius notion, a previous work has investigated the cases ρ = 0 and ρ = + ***, and shown that, while there is no solution for ρ = 0, k ≤ p *** q is a necessary and sufficient requirement when ρ = + ***, where p is the number of vertices of the grid, and q a parameter whose value depends on the actual topology of the partial grid. This paper completes our previous results by addressing the more difficult case, namely ρ = 1. It shows that k ≤ p *** 1 when q = 0, and k ≤ p *** q otherwise, is a necessary and sufficient requirement for solving the problem. More generally, the paper shows that this case is the borderline from which the considered problem can be solved.

The overall goal of the MAIS framework is to support services that are capable of adapting their behavior to changing requirements, environments, user profiles and platforms, in order to provide the user with a suitable quality of service (QoS) [112, 181, 292]. To accomplish this goal, both the front-end and the back-end MAIS environment exploit knowledge about the architecture and configuration of the underlying platform. By platform we mean of all the hardware and software system objects that support the services, for example computing nodes, interaction devices, software components and communication networks. Applications usually rely on abstractions that expose the functional aspects of the system objects. For instance, an application can display something, or send a request through a communication service. System objects also exhibit non functional aspects: in particular, basic QoS features such as bandwidth, availability, screen size, memory size, and battery level [23, 246]. Such features are subject to changes, the rate of which can go from static (e.g., the screen size of a user device) to highly dynamic (e.g., the transfer rate of a network service). In any case, the QoS of the system objects are unknown when the software components that implement the services are being developed. Therefore, in order to provide an adaptive service, such components must be capable of observing and (if possible) of controlling the QoS of the system objects they rely on [24, 25, 26]. Unfortunately, QoS is usually hidden from high-level software components. Sometimes it can be managed via tricky low-level mechanisms. In any case, there are no high-level abstractions that allow an object's QoS to be observed and controlled by high-level, platform-independent software components. To fill this gap, the MAIS project exploits a reflective architecture. The architecture is "reflective" because it allows high-level software components to observe and control the features and the inner state of the system itself. System objects are modeled by meta objects (reflective objects, or R Objects, see [251]) which expose, at a suitable level of abstraction, their meaningful features in terms of QoS. System objects and R Objects are causally connected [241]. The existence of a causal connection means that a state change in the system object causes a state change in the corresponding R Object, and vice versa. Figure 4.1 shows the various layers of the reflective system, in accordance with the general scheme sketched in Fig. 2.6. Functional objects model the functional and non reflective aspects of system objects, as exposed by the technological layer; for instance, a screen is an object where applications can display images. Reflective objects, on the other hand, model the non functional and QoS-related aspects of the system objects; for instance, a screen is modeled by its size, resolution and so on. The figure shows how the reflective mechanisms can be exploited in various ways, which will be discussed in the rest of this chapter. (Figure presented) Reflective applications rely on both domain-specific and reflective knowledge in order to provide adaptive services. Such applications exploit both functional and reflective objects. For instance, a reflective application (Reflective Application B in Fig. 4.1) can exploit both domain knowledge (e.g., user profiles) and reflective knowledge (e.g., QoS features of the devices exposed by the base reflective layer via Base R Objects) in order to provide the end user with an "optimal" service. The base reflective layer is discussed in Sect. 4.2. This approach allows sophisticated solutions to be devised, although they imply that software developers must be aware of the low-level QoS features of the underlying platform. To reduce this drawback, the extended reflective layer provides mechanisms for defining suitable QoS strategies that provide the visibility of extended R Objects. Such objects expose to the applications (Reflective Application A in Fig. 4.1) the QoS of the system objects at a higher level of abstraction. The extended reflective layer is discussed in Sect. 4.3. Reflective middleware is an intermediate tier that exploits reflective knowledge to provide applications with enhanced functional objects (i.e., functional objects with a better QoS). Non stationary distributed systems, i.e. systems where different parts exhibit great diversity in terms of message transfer delays, provide a difficult background for traditional two-tier architectures. In order to provide QoS, such as reliability and availability, for such systems we envisage the use of a three-tier architecture for service replication, where reflective middleware (i.e., an extended reflective layer) is interposed between the client layer and the end tier. The goal of this middle tier is to limit the scope of agreement protocols to well behaved parts of the system (where the middle and end tiers are located), thus relieving non reflective applications from the burden of such protocols. The three-tier scheme is represented on the right side of Fig. 4.1, where the middle tier exploits reflective knowledge to provide applications with the visibility of enhanced functional objects with improved QoS. This approach relieves the applications from the management of non functional issues, although the middle tier is bound to implement best effort policies that do not exploit domain specific knowledge. The three tier scheme for replication is discussed in Sect. 4.4. A simple example may help us to understand the two approaches. Assume that a back-end application generates a streaming video towards a front-end device. If the application itself is reflective, it can observe the QoS in detail via the appropriate R Objects and, possibly, the topology of the underlying communication subsystem as well. Therefore the application may either adapt itself to the available bandwidth (for instance, by tuning the compression rate) or control, whenever possible, the QoS of the communication subsystem (for instance, by choosing an alternate communication path). This allows the application to exploit domain knowledge (for instance, by choosing the communication path according to the requirements exposed by the user profile), at the price of a higher complexity. On the other hand, a reflective middleware layer can be interposed between the base reflective layer and the application. It would be in charge of exploiting some best-effort strategy (for instance, by choosing a communication path) in order to provide the application with a suitable QoS. The application would be simpler, as it would not have to manage reflective issues. The drawback is that the strategies implemented by the reflective middleware cannot exploit specific domain knowledge (for instance, the user profile). The proposed mechanisms can be exploited by higher-level software components, which are denoted in Fig. 4.1 as applications. In this perspective, the higher level components that implement the MAIS framework can be viewed as applications, even if they should more properly be viewed as middleware components. Section 4.2 recalls the concepts related to the computational reflection, and presents the base reflective layer. Section 4.3 describes the extended reflective layer. Section 4.4 discusses the three-tier model for replication. Finally, Section 4.5 sketches two application examples

Distributed Shared Memory abstraction (DSM) is traditionally realized through a distributed memory consistency system(MCS) on top of a message passing system. In this paper we analyze the impossibility of efficient partial replication implementation of causally consistent DSM. Efficiency is discussed in terms of control information that processes have to propagate to maintain consistency. We introduce the notions of share graph and hoop to model variable distribution and the concept of dependency chain to characterize processes that have to manage information about a variable even though they do not read or write that variable. Then, we weaken causal consistency to try to define new consistency criteria weaker enough to allow efficient partial replication implementations and strong enough to solve interesting problems. Finally, we prove that PRAM is such a criterion, and illustrate its power with the Bellman-Ford shortest path algorithm. / Les mémoires partagées réparties constituent une abstraction qui est traditionellement concrétisée par un système réparti de mémoire cohérente, au-dessus d'un système de communication par messages. Dans ce rapport, on analyse l'impossibilité d'avoir une implémentation efficace de mémoire partagée répartie à cohérence causale, basée sur la duplication partielle des variables. L'efficacité est envisagée en terme d'information contrôle qui doit être propagée pour assurer la cohérence. On introduit les notions de graphe de partage et d'arceau, qui modélisent la répartition des variables et la notion de chaîne de dépendance pour caractériser les processus qui doivent gérer des informations relatives à une variable dont ils ne possèdent pas de copie locale. Ensuite, on affaiblit le critère de cohérence causale, dans le but de déterminer un nouveau critère de cohérence qui soit suffisament faible pour permettre un implémentation efficace basée sur la duplication partielle, mais suffisament forte pour pouvoir résoudre des problèmes intéressants. Finalement, on prouve que le critère appelé PRAM satisfait ces exigences, et illustrons sa pertinence en montrant une implémentation de l'algorithme de plus court chemin de Bellman-Ford.

We present a model of a mobile ad-hoc network in which nodes can move arbitrarily on the plane with some bounded speed. We show that without any assumption on some topological stability, it is impossible to solve the geocast problem deterministically despite connectivity and no matter how slowly the nodes move. Moreover, even if each node maintains a stable connection with each of its neighbors for some period of time, it is impossible to solve the geocast problem if nodes move too fast. Additionally, we give a tradeoff lower bound which shows that the faster the nodes can move on a monodimensional space, the more costly it would be to solve the geocast problem. We provide geocasting algorithms for the case where nodes move in one dimension and also when they can move on the plane (i.e., in two dimensions). We prove correctness of our algorithms by giving exact bounds on the speed of movement. Our analysis helps understand the impact of speed of nodes, firstly, on geocasting solvability and, secondly, on the cost of geocasting. TRUE pub

International audience; This paper presents Combine, a distributed directory protocol for shared objects, designed for large-scale distributed systems. Directory protocols support move requests, allowing to write the object locally, as well as lookup requests, providing a read-only copy of the object. They have been used in distributed shared memory implementations and in data-flow implementations of distributed software transactional memory in large-scale systems. The protocol runs on an overlay tree, whose leaves are the nodes of the system; it ensures that the cost of serving a request is proportional to the cost of the shortest path between the requesting node and the serving node, in the overlay tree. The correctness of the protocol, including starvation freedom, is proved, despite asynchrony and concurrent requests. The protocol avoids race conditions by combining requests that overtake each other as they pass through the same node. Using an overlay tree with a good stretch factor yields an efficient protocol, even when requests are concurrent.

The evolution of classical information systems has introduced new technologies and services forinformation managing and sharing. With the spread of the Internet, it is now possible to easilyshare vast amounts of electronic information and computer resources in open distributed envi-ronments. These environments serve as a common platform for heterogeneous users by hostingservices, user applications and data. This evolution has opened new threats to informationsecurity and new challenges to access control modeling. In order to meet these challenges,many research works went towards extending traditional access control models towards mod-els tailored for managing data access and privilege definition within distributed and dynamicsystems.In this manuscript, we contribute to this line of research by introducing a modular frameworkfor the specification of interoperable access control policies developed autonomously in differentadministrative domains. The rule-based formalisation we propose allows for policy analysis andvalidation by verification of policy properties and simulation of execution scenarios. We havealso investigated access control in the context of collaborative decision making systems. In par-ticular, we propose a solution for controlling access in cooperating web services with transitivedependencies, as well as in data fusion processes. Finally, we consider authorization policiesand constraints related to workflow management systems and workflow-driven applications.We propose a methodology to monitor a workflow and its associated access control policy inorder to ensure a successful termination of the workflow or, if not possible, an execution witha minimal violation of the authorization constraints., L’evolution des systemes d’information classiques a introduit des nouvelles technologies et desnouveaux services pour la gestion et le partage d’informations. Avec la diffusion d’Internet, ilest desormais possible de partager facilement de grandes quantites d’informations ́electroniqueset de ressources informatiques dans des environnements distribues ouverts. Ces environnementsservent de plateforme commune pour des utilisateurs heterogenes (par exemple, les entreprises,les particuliers, etc.) en h ́ebergeant des services, des applications utilisateur et des donn ́ees.Cette evolution a introduit des nouvelles menaces pour la s ́ecurit ́e de l’information et desnouveaux d ́efis pour la modelisation du contrˆole d’acc`es. Afin de relever ces d ́efis, de nombreuxtravaux de recherche etudient l’extension des mod`eles traditionnels de contrˆole d’acc`es vers desmod`eles con ̧cus pour gerer l’acces aux donn ́ees et la d ́efinition des privil`eges dans les syst`emesdistribu ́es et dynamiques.Dans ce manuscrit, nous contribuons `a cette ligne de recherche en introduisant un formalismepour la sp ́ecification de politiques de contrˆole d’acc`es interop ́erables et d ́evelopp ́ees de mani`ereautonome dans diff ́erents domaines administratifs. La formalisation `a base de r`egles que nousproposons permet l’analyse et la validation des politiques par la v ́erification des propri ́et ́estelles que la consistance et l’efficacit ́e, ainsi que la simulation de sc ́enarios d’ex ́ecution. Nousavons ́egalement ́etudi ́e le contrˆole d’acc`es dans le contexte des syst`emes avec une prise ded ́ecision collaborative. Nous proposons notamment une solution pour le contrˆole d’acc`es dansles services web cooperatifs avec des dependances transitives, ainsi que dans les processus defusion de donnees.Enfin, nous considerons les politiques d’autorisation et les contraintes liees aux systemes degestion de flux de travail (workflows) et leurs applications. Nous proposons une methodologiepour surveiller un workflow et sa politique de controle d’acces associee, afin d’en assurer laterminaison en respectant toutes les contraintes de securite ou, si ce n’est pas possible, uneexecution avec une violation minimale de ces contraintes.

In multiprocessor computer, synchronizations between processes are needed for the access to the shared memory. Usually this is done by using locks, but there are some issues as deadlocks or lack of fault-tolerance. We are interested in implementing abstractions (as consensus or universal construction) which ease the programming of wait-free concurrent objects, without using lock but based on atomic Read/Write operations (ARW). Only using the ARW does not permit to implement wait-free consensus. The use of primitives which offer a higher power of synchronization than the ARW is needed. But these primitives are more expensive in computing time. Therefore, we are interested in this thesis in the design of algorithms which restrict the use of these primitives only to the cases where processes are in contention. These algorithms are said solo-fast. Another direction is to allow the object to abort the computation in progress - and to return a special response "abort" - when there is contention. These objects are named abortable. On the one hand we give wait-free, abortable and/or solo-fast concurrent object implementations. Indeed we proposed a universal construction which ensure to the implemented object to be abortable and solo-fast. We have also realized solo-fast consensus algorithms and abortable consensus algorithms. On the other hand, we study the space complexity of these implementations : we prove space lower bound on the implementation of abortable object and consensus., Dans un ordinateur multiprocesseur, lors de l'accès à la mémoire partagée, il faut synchroniser les entités de calcul (processus). Cela peut se faire à l'aide de verrous, mais des problèmes se posent (par exemple interblocages, mauvaise tolérance aux pannes). On s'est intéressé à l'implémentation d'abstractions (consensus et construction universelle) qui peuvent faciliter la programmation concurrente sans attente, sans utiliser de verrous mais basés sur des lectures/écritures atomiques (LEA). L'usage exclusive des LEA ne permet pas de réaliser un consensus sans attente. Néanmoins, autoriser l'usage de primitives offrant une puissance de synchronisation plus forte que des LEA, mais coûteuse en temps de calcul, le permet. Nous nous sommes donc intéressés dans cette thèse à des programmes qui limitent l'usage de ces primitives aux seules situations où les processus sont en concurrence, ces programmes sont dit solo-rapides. Une autre piste étudiée est de permettre à l'objet, lorsqu'il y a de la concurrence, de retourner une réponse spéciale "abandon" qui signifie l'abandon des calculs en cours. Ces objets sont dit abandonnables. D'une part, nous donnons des implémentations d'objets concurrents sans attente, abandonnables et/ou solo-rapides. Pour cela, nous proposons une construction universelle qui assure à l'objet implémenté d'être abandonnable et solo-rapide ; nous avons réalisés des algorithmes de consensus solo-rapides et des algorithmes de consensus abandonnable. D'autre part nous étudions la complexité en espace de ces implémentations en proposant des bornes inférieures sur l'implémentation des objets abandonnables et sur le consensus.