Thesis of Léon Lim

29 November 2012

The thesis will be defended by Léon Lim on Thursday 29th of November, 2012.

Subject: Partitionable Group Membership in Mobile Ad hoc Networks

The thesis will be defended on Thursday 29th of November, 2012 at 2 PM in Télécom SudParis, 9 rue Charles Fourier, 91000 Evry, room C06 with the board:

Pascal Felber, Professor, Université de Neuchâtel, Reporter
Achour Mostefaoui, Professor, Université de Nantes, Reporter
Pierre Sens, Professor, Université Pierre et Marie Curie, Examiner
André Schiper, Professor, Ecole Polytechnique Fédérale de Lausanne, Examiner
Guy Bernard, Professor, Télécom SudParis, Thesis Director
Denis Conan, Assistant Professor, Télécom SudParis, Supervisor

Abstract:

In Mobile Ad hoc NETworks or MANETs, partitionable group membership is a basic service for building partition-tolerant applications—i.e., severals groups of processes evolve concurrently and independently of each other. Since two decades, severals partitionable group membership specifications have been
proposed. However, none of them satisfies the two following antagonistic requirements: 1) it must be strong enough to simplify the design of partition-tolerant distributed applications in partitionable systems; 2) it must be weak enough to be implementable. This thesis studies partitionable group membership in very dynamic network environment such as MANETs.

After an in-depth study of the problems in the specifications proposed in the literature and identifying the characteristics of MANETs, we propose a solution to the problem of partitionable group membership by adapting Paxos for such systems. To this means, we develop a system model that characterises stability in MANETs. Mobile nodes (processes) that stay in a partition during a period that lasts long enough are said to be stable. A stability criterion based on heartbeats counting is also proposed to select the most stable nodes—i.e., nodes that could be part of a potential stable partition. Since stable and unstable nodes can coexist in the context of a partition, we define a weak stability condition of α stable processes in a partition which guarantees the progress and termination of executions even if the partition is not completely stable.

Then, the adaptation of Paxos results in a specification of abortable consensus AC which is constructed on the eventual α partition-participants detector ♢PPD and the eventual register per partition ♢RPP. ♢PPD guarantees liveness in a partition even if the partition is non completely stable whereas ♢RPP ensures safety in the same partition. The role of ♢PPD is to make trade-offs between agreement and progress by eventually detecting the stability condition, and eventually providing the leader among them. ♢RPP provides a distributed storage (or register) in a partition.

Finally, partitionable group membership is solved by transforming it into a sequence of abortable consensus instances AC, where each AC instance is executed by the participant nodes in the potential successor view. When the decision returned by the abortable consensus is a set of processes α-Set associated with an identifier, these processes and the identifier constitute the successor view.
The decision could be a specific value (⊥,⊥) meaning that the consensus has aborted because the stability condition is not satisfied. Each of the modules ♢PPD, ♢RPP, AC, and partitionable group membership is implanted and proved. Next, we analyse the performances of α by simulation.

Keywords: MANETs, dynamic partitionable systems, partitionable group membership, abortable consensus.

Events