ASAP – As Scalable As Possible

Opportunistic networks exploit human mobility and consequent device-to-device ad hoc contacts to disseminate content in a ”store-carry-forward” fashion. In opportunistic networks, disconnections and highly variable delays caused by human mobility are the norm. Another major challenge in opportunistic communications arises from the small form factor of mobile devices which introduces resource limitations compared to static computing systems. Lastly, human mobility and social interactions have a large impact on the structure and performance of opportunistic networks, hence, understanding these phenomena is crucial for the design of efficient algorithms and applications.

In this work, we take an experimental approach to better understand opportunistic mobile social networks. We design and implement of MobiClique, a communication middleware for opportunistic mobile social networking. MobiClique takes advantage of user mobility and social relationships to forward messages in an opportunistic manner. We perform a large-scale MobiClique experiment with 80 people, where we collect social network information (i.e. their Facebook profiles), and ad hoc contact and communication traces. We use the collected data with three other data sets to analyse in detail epidemic content dissemination in opportunistic networks. Most of the related works have focused on the pairwise contact history among users in conference or campus environments. We claim that given the density of these networks, this approach leads to a biased understanding of the content dissemination process. We design a methodology to break the contact traces down into “temporal communities”, i.e., groups of people who meet periodically during an experiment. We show that these communities correlate with people’s social communities. As in previous works, we observe that efficient content dissemination is mostly due to high contact rate users. However, we show that high contact rate users that are more frequently involved in temporal communities contribute less to the dissemination process, leading us to conjecture that social communities tend to limit the efficiency of content dissemination in opportunistic mobile social networks.

Directeur de Thèse :
– Michel Raynal, professeur Université de Rennes 1
Rapporteurs:

• Dominique Mery, Professeur Loria
• Franck Petit, Professeur Lip6

Examinateurs :

• Carole Deplorte, Professeur Paris Diderot
• Petr Kuznetsov, Chercheur TU Berlin
• Rachid Guerraoui, Professeur EPFL Lausanne
• Panagiota Fatourou, Assistant Professeur, University of Crete

Dans un système distribué, différents processus communiquent et se synchronisent pour résoudre un calcul global. La difficulté vient du fait qu’un processus ne connait pas les entrées des autres. Nous considérons ici un système asynchrone: on ne fait aucune hypothèses sur les vitesses d’exécution relatives des différents processus. De plus, pour modéliser les pannes, nous considérons que les processus peuvent crasher: ils peuvent arrêter leur exécution à n’importe quel endroit de leur programme.

Dans l’étude théorique des systèmes distribués, les problèmes doivent être considérés selon deux aspects: la sûreté et la progression. La sûreté définit quand une valeur de sortie est correcte. La progression définit dans quelles conditions un processus doit terminer une opération, indépendamment de la valeur qu’il choisit comme sortie.

Cette thèse se concentre sur les liens entre calculabilité et conditions de progression des objets distribués. Dans un premier temps, nous introduisons et étudions la notion de conditions de progression asymétriques: des conditions de progression qui peuvent être différentes pour différents processus du système. Nous étudions ensuite la possibilité de
fournir des abstractions dans un système donné. La question de l’équivalence de modèles de systèmes est ensuite abordée, en particulier dans le cas où les processus ont accès à des objets puissants. Pour finir, la thèse traite le sujet des tâches colorées en fournissant un algorithme de renommage adapté au cas où la concurrence est réduite. Une nouvelle classe de tâches colorées est enfin introduite qui englobe, sous un formalisme unique, plusieurs problèmes considérés jusqu’ici comme indépendants.

Calculability and progress conditions of shared objects when facing crashes

In a distributed system, different processes synchronize in order to solve a global computation. The difficulty comes from the fact that a process does not know the other inputs. We consider here asynchronous systems: no assumption can be made regarding the relative speeds of processes. We also consider that processes can crash, i.e. stop their execution at an arbitrary point of their code.

In the theoretical study of distributed systems, problems have to be considered according to two aspects: safety and progress. Safety defines whether a given value can be output. Progress defines under which conditions a process is required to terminate its operation, regardless of the value it outputs.

This thesis is about the links between calculability and progress conditions of shared objects. We start by introducing and studying the notion of asymmetric progress conditions: progress conditions that don’t necessarily impose the same requirements for different processes. We then study the possibility of supplying processes with abstractions in a given model. The issue of the equivalence of system models is then raised, especially when processes have access to strong objects. Finally, the thesis studies colored tasks. It presents a renaming algorithm that terminates if contention gets below a given threshold. It then introduces a new class of colored tasks that allows to unify in a single framework different problems which were previously studied independently.