HiCo-MoG : Hierarchical consensus-based group membership service in mobile Ad Hoc networks

Abstract

Group Communication System (GCS) is largely recognized as fundamental support in fault tolerance solutions. The need for such a system arises not only in wired networks but also in mobile Ad-Hoc networks. The design of this service becomes more complex in these networks because of their very dynamic topology and limited energy autonomy. Group Membership service is considered as a significant part of the GCS. In this paper, we propose HiCo-MoG (Hierarchical Consensus for Mobile Group): an efficient solution for group membership in large mobile Ad-Hoc Network (MANET). While the group membership problem is also equivalent to Consensus, we use the Dynamic Hierarchical Consensus called (HCD) with dynamic clusterheads set for designing a group membership service for MANETs. The HCD protocol achieves consensus using the clusters provided by a new failure detector called $◇ C$ . Each group member can obtain a consistent view of the group by executing the consensus protocol. We demonstrate the efficiency of our method in term of scalability and fault tolerance.

Keywords

Group communication system group membership hierarchical consensus MANETs HiCo-MoG

1. Introduction

Recent progress of laptop computers and mobile networks technology bring to great steps the users in the world of mobile processing. The introduction of mobile users provides a large flexibility and availability for group applications. Mobile Ad-Hoc Network (or MANET) [30,33] is a set of mobile nodes which communicate with each other without assistance of any fixed infrastructure. Each node in the network can directly communicate with only its neighbors, i.e. nodes which are in its communication range. If a direct communication link cannot be established, then a multi-hop routing scheme is used. As opposed to traditional networks, nodes in MANETs are constrained in their energy availability, memory, computational resources, and communication bandwidth. Also, the topology of the network can change frequently.

MANET is established “on the fly” by a group of mobile nodes. It is organized as a group of nodes created on demand and is thus naturally based on group communication model. Each node in the network can join and leave the group freely. Additionally, MANETs are inherently scalable; there is no upper bound on the number of nodes composed the network. A group is a set of processes which are said to be members of the group. Group communication services are useful for building applications that require reliable multipoint communication among a group (or groups) of processes. The design of reliable Group Communication Systems (GCS) is already difficult in the case of wired networks. It becomes more complex in MANETs and the existing group communication systems were not considered in these networks. Group membership service is a significant part of GCS. It maintains information about the nodes that belong to the group and delivers the message to them. In MANETs, group membership changes frequently due to nodes mobility, and unreliable wireless communications links. The group management service must be effective in resources utilization and able to minimize the effect of group membership changes on the members.

In [13], it is shown that the group membership problem is equivalent to Consensus. The consensus is one of fundamental fault-tolerant problem arising from many distributed computing systems. It is considered as a basic building bloc for resolving agreement problems. However, it has been proved that in asynchronous distributed system, the consensus problem cannot be solved deterministically even with only one process crash [20]. To overcome this impossibility, several oracles have been proposed including Unreliable Failure Detectors (FD) [15]. FD are introduced as a mechanism that provides (possibly incorrect) information about processes failures. So, they were characterized in terms of two properties: completeness and accuracy. Completeness characterizes the failure detector capability of suspecting every incorrect process, while accuracy characterizes the failure detector capability of not suspecting correct processes i.e., restricts the mistakes that the failure detector can make. Unreliable failure detectors, when satisfying these properties on completeness and accuracy, can be used to solve several agreement problems in asynchronous distributed systems, in particular the consensus and group membership problems [13,17]. $◇ S$ [14] is a weakest and commonly used failure detector class called Eventually Strong which satisfies strong completeness and eventual weak accuracy. There is a time after which some correct processes are not suspected by any correct process. Nevertheless, the provided information list of suspected processes that have crashed is not always up-to-date or correct (e.g., an FD may falsely suspect a process that is alive), due to the high unpredictability of message delays, the dynamic and changing network topology, and the high probability of network message losses. Moreover, the unreliable FD can be slow, i.e., it may take a long time to suspect a process that has crashed, and it can make mistakes by falsely suspecting correct processes or trusting crashed processes. To be useful, any failure detector has to be reasonably fast and accurate.

FD are classical mechanisms that also provide information about processes failures and can help systems to cope with the high dynamics of MANETs. In [40,41] hierarchical solutions for solving the consensus problem in MANETs are proposed. These are the first two works that have been reported on deterministically achieving consensus in MANETs. So, the authors consider a hierarchical network with fixed clusterheads in [41] and with dynamic clusterheads in [40]. The dynamic solution is an improved version called HCD. It consists of a modular approach that separates the concerns of clustering hosts from achieving consensus by means of new FD called $◇ C$ . The HCD architecture facilitates the design of hierarchical protocol by providing the fault-tolerant clustering function transparently. The major challenge in the implementation is how to dynamically select clusterheads. For this end, the authors proposed a clustering algorithm based on the failure detector $◇ C$ which in turn based on $◇ S$ . In their work, clusterheads are used not only for simply forwarding messages, but also synchronizing the cluster members for the message exchange steps in achieving consensus. To deal with overhead cost generated by exchanged consensus messages, the size of these messages are merged/unmerged in clusterheads and consequently do not disturb regular communications.

In mobile environment, group applications should be able to tailor the GCS according to its needs not only in terms of timeliness, reliability and security. To cope with the needs of modern applications, GCSs need to be scalable, robust, and flexible [11,22]. Although many collaborative applications in MANETs do not require stringent synchronization guarantees and fully-connected of all members, which allows members to agree on a shared approximation of the group membership [23]. Reaching agreement on the group membership in the presence of failures for large network is difficult. As the network is very dynamic and inherently scalable, it becomes critical and necessary to have some efficient mechanisms that quickly detect node failures to maintain dynamically group membership consistency. The movement event that causes frequent connections or disconnections of nodes must also be taken into count.

In this paper, we propose HiCo-MoG: a new group membership service for MANETs. We believe that with an efficient clustering architecture and the means of deterministic consensus for an agreement on a global consistent view, we can carry out a simple and more effective solution for group membership responding to applications needs. The group members are organized into clusters (or sub-groups) in the deployment area of members through $◇ C$ . After having presented the problem statement and related work in the second section, we present the background in the third section. The system model is described in the fourth section. Then the description of HiCo-MoG including the problem specification, steps of group management and algorithm is given in the fifth section. The section six describes the results achieved and discussions. Finally we concluded our paper with future work in the last section.

2. Problem statement and related work

In this section, we will first give a definition of the problem and then a review of the related research.

2.1. Problem statement

The design of reliable and efficient GCS is a true challenge in MANETs. Compared with fixed networks, as the network is very dynamic, group membership changes frequently due to nodes mobility and unreliable wireless communications links. The difficulty lies especially in handling the mobility of devices [1]. If a mobile host moves from one cell to another during the agreement in group membership, it can cause frequent changes in the group composition, since it is often difficult to distinguish between a crashed host and the slow one due to handoffs. Some work assumes a handoff agent who was supposed to be responsible in supervising the movement of mobile hosts between cells and reports the changes, which these movements generate on the current view to the membership agent. The membership agent is responsible for detecting the causes of a change of view: join and leave of mobile sites, failures reported by the FD and mobility reported by the handoff agent. Consequently, the system must distinguish between disconnections and failures, the fact that temporary disconnection of a member causes him to leave the group and join it in a reduced time [7]. In addition, as a MANET is often large, different members may have contradicting and asymmetric perceptions of the group’s membership according to their relative location. This injects inaccuracy in determining the group membership and exacerbates the time required to agree on the current membership. It is therefore necessary to have mechanisms that maintain group membership consistency. Also, because of the scalability problem, the group membership service should be effective in resources consumption. These additional constraints should be considered in MANETs distributed algorithms of group membership problem.

Several studies in group communication show that it is not practical to manage and assure consistency of the global group view (the list of all group members) in large MANETs, without subdividing the entire group into sub-groups managed locally. The main advantage of this subdivision is that any change in sub-group composition does not require the recalculation of the entire group membership or some other local views. Unfortunately, it is well recognized in group management as well as security of group communication that the role of a group controller is significant. This controller should be elected in MANET. However, solutions based only on one controller are not scalable. This promotes the subdivision of the whole group into sub-groups or clusters with multiple controllers (or leaders), which requires both the management of each sub-group and the communication between them. In our case, these leaders are the clusterheads set that are easily provided by the used failure detectors without using an election algorithm.

2.2. Related work

In the early stage of the development of group communications systems, small groups were used for providing replicated services, fault-tolerance and data replication. These groups have static configurations; join and leave were rare events. After that, dynamic systems have gained attention in many research areas. With the emerging of world-wide communication technology, new applications aim to allow users to freely join and leave any group. Actually, the group concept proved to be very useful and dynamic systems with large groups with many participants were emerged [11,19,38]. GCS has been well-studied for static, wired networks [17]. For WAN, the first well proposed approach is Moshe [27]. It is characterized by a client/server architecture, in which servers are in charge of maintaining client membership. It relies on a network event mechanism specific for a WAN, which keeps servers informed about changes to the group and performs as an eventually perfect failure detector. Few works have been done on the development of distributed services, such as group communication in mobile environment. In MANETs, research in this direction remains relatively new.

Mobile groups are an extension of traditional group’s concept to the mobile environment. In this case, more issues in group membership need to be considered because they are different from those in traditional one. First, mobile hosts such as laptop computers, PDAs, and mobile phones have severe resource constraints in terms of energy and processing capabilities. Second, wireless communication involves high error rate and limited bandwidth problems. Third, mobile environment is known by the movement of its devices. All these additional constraints should be considered in MANETs distributed algorithms related to group membership problem. In the group communication models, the total ordering of messages at nodes is required to maintain the global consistency of the group views. This service of group communication is an important complement of group membership service. In this context, some solutions have been proposed either for mobile or P2P systems [6,10]. Prakash and Baldoni [32] used location information in the determination of group membership of a mobile system when the network stays connected. They provide a first attempt to define a location-based group membership service. It is assumed that the network stays connected and there are no failures. Only changes due to mobility are considered. The architecture proposed is composed of a proximity layer between the group membership layer and the underlying mobile network.

At the beginning, group communication in MANETs have extended traditional GCS to deal with mobility to ensure reliable communications. Roman et al. in [34] have proposed a solution to address the unpredictable nature of wireless networks in Ad Hoc mode versus mobile entity discovery. An entity is considered to be within the communication range of another if the two are within a specified distance of each other called a safe distance. This criterion is determined by the signal strength of messages received via a connection without a direct connection (i.e., without using base stations or routing protocols to relay messages). This intensity depends on the distance between the transmitter and receiver. Therefore based on the signal strength, a mobile entity receiving a message can determine the proximity of its transmitter. Entities whose messages are received with low intensity are not retained, as it is assumed that they have a high probability of becoming inaccessible in the future. In the same context, [24] provided the specification for a partitionable group membership service supporting Ad-Hoc mobile applications and proposed a protocol for implementing the service.

[7] have proposed a protocol to solve the problem of reliable communication among a set of unbounded processes forming a group in a dynamic system. The problem is studied in a setting where communication links model a temporary disconnection among group members. In some other solutions, groups are formed according to several attributes[8,29]. Local attributes are applied to individual devices like: location, proximity, available resources and global attributes applied to the whole group: group size and reputation. Solutions of GCS using this approach considers only one leader controlling all group members and do not show their effectiveness for a scale network.

Recently, [23] presented a group membership service based on partial member connectivity that allows members to agree on a shared approximation of the group membership. Their main idea is to separate node discovery and connectivity from the membership service. This allows members to agree a shared approximation of the group membership. [28] proposed a new group membership model that takes into account the formation of dynamic paths to deal with the network partition. Their solution avoids capricious views installation during stable periods because the removal or inclusion of a process is allowed only if this process was suspected to leave or join the partition. Based on this idea, [3,39] proposed a dynamic group membership service for vehicle coordination. They defined and evaluated by simulations a set of criteria concerned with the correctness and performance of the views produced by the protocol to be satisfied. [2] proposed a toolset for mobile systems testing. It consists of a scenario-based approach that is well suited for describing the behaviour and interactions to observe in distributed systems. The approach is demonstrated on a case study whose specification are detailed in [24].

3. Background

3.1. View oriented GCS

GCS constitutes a significant block for dynamic distributed systems. It provides two main services [17]:

Group membership: the group members are provided with the list of all current group members, called view, and are notified about any membership changes. This group membership can change due join/leave operations; voluntary or involuntary departure but also due to the communication and process failure.

Reliable and ordered message delivery: at least causal ordered of messages is important in any kind of distributed system. This means if the content of message m is dependent on the content of message $m^{'}$ then each process should receive $m^{'}$ before receiving m.

Group membership service is considered as a significant part of the GCS, it manages the formation and maintenance of currently active and connected group members called view, and also informs the applications of the updated view whenever it changes. The view-oriented group communication systems are used to realize the fault-tolerant distributed computing systems [6,31]. For a given group, a view includes the identifier and a list of currently active and connected members; these identifiers distinguish between different instances of the same membership set. The following group membership change events should be considered:

Join: one process sends a request to join the group;

Merge: two or more groups are organized into one group;

Leave: one member leaves the group;

Partition: the group is divided into two or more independent groups.

On each change of membership, a specific protocol is executed.

3.2. Group membership as consensus

In distributed systems, group membership has been extensively investigated as an underlying mechanism for achieving consensus through a concept known as virtual synchrony [23]. It imposes that view change events are delivered in a consistent order with respect to the flow of messages. Consensus and reliable broadcast have been considered for the first time in static groups. After that, systems with dynamic groups extend this model by providing explicit join and leave operations to adapt the group membership over time. Moreover, such systems can exclude faulty processes automatically from the membership. So, still reaching agreement on the group membership in the presence of failures is not trivial. Two approaches have been considered [12]:

Run a consensus protocol among the all previous group members to agree on the future group membership. This is the canonical approach, it tolerates further failures during the membership change, but involves the potentially expensive consensus primitive.

Integrate consensus with the membership protocol and run it only among the correct members. Since this consensus algorithm doesn’t need to tolerate failures, it can be simpler; because further failures may still occur, it provides different guarantees.

It has been demonstrated in [13] that reducing membership to consensus in an interesting way rather than developing complex membership protocols. In this case, decoupling “failure detectors” from “membership exclusion” is favoured. So,the membership problem can be seen as a consensus problem. Despite they are different, solving consensus can help in solving group membership by transforming it into a sequence of consensus, where each consensus is executed by the processes in the current view and the decision returned by the consensus is a set of processes [36]. Precisely, if we consider the current membership view

v_{i}

and the problem of defining the next membership view

v^{i + 1}

, this can be seen as a consensus problem among processes in

v^{i}

, where the initial value of each process is a proposal for the next view [35]. The mobile environment is considered as dynamic distributed systems [8,21,40]. As a result of the mobility, the resource constraints and the wireless connection, dynamic distributed systems usually include unavailable and unreliable nodes and links, unknown or unbounded membership and infinite arrival. In fact, the additional characteristics of dynamic systems are not anomalies but rather integral part of the nature of the system.

3.3. Overview of HCD

$◇ C$ FD [40] is a powerful oracle for hierarchical solutions when comparing it with other failure detectors recently proposed to MANETs [9,18]. It has the responsibilities of detecting the failures of host members and constructing a cluster-based on the two-level hierarchy. So, group members will be grouped into clusters with clusterheads in each cluster. As shown in Fig. 1, each host is associated with an eventual clustered oracle module. On the query from a host $m_{i}$ , the clustered oracle module returns three outputs: $◇ C$ : CH, $◇ C$ : trusted and $◇ C$ : clusterhead. The figure illustrates the FD architecture and the signification of there outputs. Different from the existing work, the clusterhead hosts are dynamically selected by $◇ C$ . It can reach a Global Stabilization Time (GST). Before this time, different processes may have different $◇ C$ : CH sets. However, after GST, all the correct hosts get the same stable $◇ C$ : CH. Then, all the correct hosts have the same $◇ C$ : CH and each correct host associated with a correct clusterhead in $◇ C$ : clusterhead. Due to host failures, false suspensions or the movement, a clusterhead may be removed from the $◇ C$ : CH. Upon a mobile hosts detects the deletion of a local clusterhead, it will switch to a new cluster. Moreover, if a host finds that its current clusterhead is no longer the nearest one, it will change its cluster. So the member will choose the nearest one in $◇ C$ : CH and starts the join procedure.

The HCD protocol [40] achieves consensus in MANETs using the clusters constructed by $◇ C$ . Due to failures and mobility of nodes, a mobile host may needs to switch clusters that are dynamic at any time. Like the existing FD-based consensus protocols, HCD adopts the rotating coordinator paradigm and executes in asynchronous rounds until a decision is reached. Each round is coordinated by a predetermined Mobile Host (MH) that tries to impose a decision value. During a round $r_{i}$ , the cooperation between processes is based on the output of failure detector $◇ C$ . HCD protocol is based on HMR [26]. It presents a unified approach to achieving a consensus with two orthogonal versatility dimensions. The versatility is achieved by letting two sets D (the set of hosts that need to check the decision status), and A (determines the message exchange pattern: centralized or decentralized). Consequently, HCD can be considered as GAF [25]. GAF is a general agreement framework based on the well-known Chandra–Toueg’s consensus protocol [14], denoted CT.

Fig. 1.

$◇ C$ architecture.

Fig. 2.

HCD protocol.

Each round of HCD protocol is divided into four concurrent tasks. Figure 2 shows an illustrative example that describes the types of exchanged messages between either an ordinary member or a clusterhead in each task. The designation of the coordinator host in each round is deterministic and can be allocated to the nodes in a rotating manner. Note that some mobile hosts may be in different rounds at a given time. In each round, some hosts values are sent through proposal messages with necessary parameters until the decision condition is reached. At this time, the decision value is broadcasted to all other alive hosts.

Like the most consensus protocols, Task1 is executed in asynchronous rounds. The figure shows task1 as the execution of the consensus algorithm in a round $r_{i}$ . It is composed of two phases. According to the output of the $◇ C$ , in phase1 three types of messages are exchanged: PROP is the proposal message sent from clusterhead ${CH}_{i}$ to its local hosts. PROPG is a proposal message sent by the coordinator to all the cluserheads. NEWR is the message used to lead mobile hosts to a new round. During this phase, if the mobile host is the coordinator, it sends PROPG to all the clusterheads; otherwise, it sends NEWR to the coordinator, for a possible jump to a new round. Each clusterhead ${CH}_{i}$ waits for the reception of the PROPG message from the coordinator unless the coordinator is suspected or it is no longer a clusterhead. So, it sends out the PROP message to all its local hosts, either with the received estimation in PROPG or without any estimation in the other case. Each mobile host either receives this message so updates its estimation and round values, or it switches to another cluster. The role of phase2 is to send the confirmation ECHO messages to their clusterheads. These messages are merged to ECHOG in each clusterhead and sent out to the DA set for an eventual decision. In this case, Task2 allows the consensus decision value to be reliably broadcasted to all mobile hosts. As presented in the figure, Task3 manages received late ECHO messages. After receiving such a message, any mobile host if has changed the clusterhead, forwards it to the new one. Otherwise, it constructs a redeeming ECHOG message and sends it to the DA set. Task4 manages the future messages corresponding to mobile hosts in rounds more recent than its own. When a mobile host receives a late message: If the host is not a clusterhead and the message is not a NEWR one, it forwards it to all its local hosts. If it is not in the DA set of the previous round of the received message, or the current round of the mobile host is less then the previous round of the message, it sends an ECHO to its clusterhead and jumps to execute the task1 for run the consensus and eventually decide on a recent estimation.

3.4. Security issues

GCSs are widely recognized as fundamental in fault tolerance solutions. In any distributed system, security and fault tolerance address similar issues: keeping the system operational in the case of attacks or failures. The particular nature of Ad-Hoc networks in mobility and vulnerability to attacks makes it much more necessary to take the security aspect into account. In MANETs, group communications should be secured and a group key shared between members is required. Group key management is a basic building block for the security of group communications. It requires the existence of group communication support for the establishment of the group key. The group management service is therefore a fundamental support for group key management protocols. It ensures the delivery of communications to all operational members of the group and provides the correct list of them after each alteration in the composition of the group. These two problems are generally treated independently. Some studies have shown the importance of exploring the impact of group characteristics on key management and link security to other aspects of group management [37]. So, it is clear that it is not effective to provide solutions and propose security protocols without taking into account the aspect of the group characteristics. Our group membership service can be used as support for group communication security solutions in Ad-Hoc networks.

4. System model

The system model of HiCo-MoG is considered as an asynchronous MANET with unbounded set of mobile hosts MHs, $MH s = {MH}_{1}, {MH}_{2}, \dots .$ At any given time, only a subset of $MH s$ participates in the group communication. The system is equipped with unreliable failure detector $◇ C$ . There is at least one correct host in the system. The nodes communicate by radio broadcast with equal and finite transmission range. The network topology is dynamic, and communication channels are assumed to be reliable (i.e. exchanged messages are not changed, created or losses). For instance, only one group G is considered. A MH can only fail by crashing, but they still act correctly until it crashed. Crashes are assumed to be definitive i.e. Byzantine failures are not considered. The mobility of hosts is fully taken into account by the clustering algorithm of $◇ C$ . The clusters are formed dynamically according to $◇ C$ clustering algorithm, details are in [40]. $◇ C$ allows the movement of group members between clusters. So, the clusterheads set and the corresponding members in each cluster are updated automatically. Whenever a MH changes its clusterhead, it may be suspected in its first cluster. Due to a disconnection for example, it will not inform its clusterhead. However, when it connects to another cluster it will be deleted from the suspected list of $◇ C$ and is considered as false suspicion. Hence this member remains in the group view since the disconnection/connection is done in a short time. Equally, if a member is suspected faulty, it is removed from its cluster and the new clusterhead can be selected. Fortunately, many collaborative applications do not require stringent synchronization guarantees in MANETs. It is for this reason that we have not added a primitive specific to the movement of hosts.

The remaining group membership events are managed by our algorithm that collaborates strongly with HCD algorithm. In addition to the mobility event, a MH can exited the group by invoking the leave operation or by crashing. A MH can invoke only two operations: ${Join}_{G}$ and ${Leave}_{G}$ , other group membership events namely Merge and Partition can be considered respectively as a sequence of ${Join}_{G}$ and ${Leave}_{G}$ operations. If a member leaves or is discarded from the group, all remaining members should be informed about this event and agree on a new view. Accordingly, if a new member is detected, all current members should receive some messages about this event before all of them agree on its joining and the new member is added to the membership set. We assume also that the virtual synchrony property is assured. This imposes that view change events are delivered in a consistent order with respect to the flow of messages.

5. Description of HiCo-MoG

HiCo-MoG is focused on the environment where a large number of mobile hosts are organized in two hierarchical levels according to the clustering architecture. As required by the mobile group applications. Such environment requires scalable, robust and consistent group membership service. We therefore give the specification of HiCo-MoG algorithm and the correctness proof.

5.1. Problem specification

The variety of proposed specification for the group membership problem responds to the diverse requirements of their applications [5]. The specification of the problem is not unique. On the contrary, multiple definitions and implementations exist, depending on the type of system for which they are devised. The first attempt for unifying the specification properties of group membership services is given in the survey of Chockler et al. [17]. They identify a series of basic properties to be satisfied by every membership or group communication services. In the case of dynamic group membership, reaching agreement on the group membership in the presence of failures is not trivial. In our work, we adopt the basic specification of the group membership problem defined in [17,27]. Accordingly, like as any problem of distributed system, this specification concerns of safety and liveness properties:

Property 1 (Self Inclusion).

A host is member of each view it installs. This property requires the membership service to inform each mobile host of only those views of which the host is a member. Formally: if $m_{i}$ installs a new view V, then $m_{i} \in V$ .

Property 2 (Initial View Event).

Each event occurs in some view context.

Property 3 (Local Monotonicity).

Two committed views are never installed in different order by two different hosts: The local monotonicity property requires that the sequence of views delivered to each client during an execution should be the same. It allows mobile hosts to determine which of two given views is more recent, by comparing their view identifiers. Formally: If $m_{i}$ installs a view V with identifier $id$ after installing a view $V^{'}$ with identifier ${id}^{'}$ , then $V_{id} > V_{{id}^{'}}^{'}$

Property 4 (View Agreement).

Means that group members share the same perception of the group membership.

A mobile host does not install a view unless the immediately previous one has been installed by all other mobile hosts contained in both views.

If some mobile hosts contained in a committed view does not install it, or installs a different view as its immediate successor, all hosts in the former view will eventually install a new view as the immediate successor to the first one.

Property 5 (Membership Precision).

If the system contains stable components, i.e. subset of hosts that remain correct and connected, the same correct view is installed as the last one in every host of the same component. The liveness property of the membership information depends on the eventually perfect execution of the failure detector. Formally: For every stable component $S \subseteq M$ , where M is set of mobile hosts, there exists a view $V = S$ such that for all $m_{i} \in S$ :

$m_{i}$ installs V as its last view; and

every message that $m_{i}$ sends is received by every other process in V

5.2. Notations

We use the notations in Table 1. for the description of HiCo-MoG algorithm.

Table 1
Symbol notations

${Join}_{G}$ message sent by a $MH$ to its neighbors informing him about its intention to join the group G

${Leave}_{G}$ message sent by a $MH$ to its clusterHead informing him about its intention to leave the group G

J the set of members that have sent a ${Join}_{G}$

L the set of members that have sent a ${Leave}_{G}$

$J & L$ the merged message containing the two sets J and L

${Discovery}_{G}$ message sent by the initiator to inform the mobile hosts about its intention to create the group G

${Confirm}_{G}$ message sent to the initiator informing him about its intention to join the group G

$MH$ a mobile host (a node)

${VM}_{i}$ the view installed by ${MH}_{i}$ , it’s made of two fields: ${VM}_{i} . id$ (its identity) and ${VM}_{i} . members$ (its composition)

$◇ C . {CH}_{i}$ the actual list of designed clusterheads, it’s the output of the failure detector $◇ C$ associated to ${MH}_{i}$

$◇ C . {clusterhead}_{i}$ the actual clusterhead of ${MH}_{i}$ , it’s the output of $◇ C$

$HCD (VM)$ the call of the HCD protocol with $VM$ as the proposed input parameter

$send (m)$ primitive that sends the message m

5.3. Group management steps

HiCo-MoG uses a two-level hierarchical structure of MHs as it’s based on HCD: clusterheads (or leaders of sub-groups) and other MHs considered as clients, each client belongs to only one cluster. It considers the group membership service defined by some attributes as needed by the application [8,29]. The formation of the group G is accomplished according to three stages: group member’s discovery, group initialization and dynamic group management: Group member’s discovery.

The group formation is started by a group initiator which launches member’s discovery by diffusing a message ${Discovery}_{G}$ containing the desired group attributes. The initiator sets a timeout which limits the time wait for collecting responses. Any MH receiving this message checks the conformity of attributes with its local constraints and confirms its initiator by a ${Confirm}_{G}$ message containing its identifier and its other information like the location. At the end of this phase, the initiator will have some informations about group nodes forming an initial group view.

Group initialization.

One of the important task of the group initialization is to enforce global group constraints like group size and reputation. This phase does not start until the initiator has received responses from hosts in its nearby members. If the attributes are in conformity, it sets its initial view to members responding by positive acknowledgement, and sends it to members which in turn lunch the consensus to agree on the view. Otherwise, the group is ready to be subdivided.

Dynamic management of the group.

Assures the group maintenance according to join/leave events and the output of the failure detector. After every alteration in group composition, members agree on the next view that is the output of consensus decision.

Figure 3 illustrates these three stages: Fig. 3(a) shows an initiator who wants to form the group. So it sends a discovery message containing the desired attributes to its vicinity formed by its neighbors. This message will be propagated in the neighborhood to inform other nodes about the creation of a corresponding group. After checking the attributes, hosts that want to join this group send a confirmation message to the initiator. Figure 3(b) shows the group initialization. It depicts an example of the group separated into two sub-groups. Group size attribute may be the main cause of this splitting. In each sub-group a leader is designated as the clusterhead. Figure 3(c) indicates the third stage corresponding to a possible update of the group composition after the group initialization step. It shows three clusters associated with their new clusterheads.

Fig. 3.

Group formation stages.

5.4. Group membership algorithm

Algorithm 1:

HiCo-MoG algorithm

HiCo-MoG algorithm (Algorithm 1) consists of three tasks: Task1 is the discovery step of the group G. At that time, a timeout is set to a constant value that determines a waiting time for collecting members wishing to join the group. A member that confirms to the initiator, initializes his view to its identity. Then, after the initiator receives ${confirm}_{G}$ , the corresponding mobile host is added to the initial view of the group ${VM}_{i} .1$ . Task2 is executed only by the initiator; it proposes itself as a clusterhead by initializing $◇ C$ at its identity and sends the obtained view in Task1 to all members in the view. So, when the group is initialized, every member has the initial view ${VM}_{1}$ containing the initial snapshot of the membership as the current view. Task3 guarantees the view consistency of the group membership by guaranteeing that all members contained in the view share the same perception of the group membership. Join and leave events are treated by clusterheads $◇ C : CH$ , any MH that receives these events forwards it to its clusterhead $◇ C : clusterhead$ .

On receiving ${Join}_{G}$ or ${Leave}_{G}$ by any clusterhead member, it sends it to the clusterheads set $◇ C : CH$ . In this way, all correct clusterheads will be quickly informed of these events. After it has invoked the ${Join}_{G}$ operation, a MH knows it belongs to the group when it receives the decision of consensus HCD(V), where V is the proposed view of the group on which active members must agree. In all cases, Task3 is repeatedly executed by members (whether they are clusterhead or not) during the group existence. The algorithm guarantees view consistency by calling the consensus protocol after each assignment of the group composition. The new view is installed after receiving the decision of consensus. It will be forwarded by a reliable broadcast primitive of the HCD protocol. Additionally to join and leave events, failures are taken into account by $◇ C$ . While for mobility, the clustering algorithm assures the members switching between clusterheads as well as the election of new clusterheads and eventually deleting or adding the new clusters. In order to improve the readability of HiCo-MoG algorithm, Fig. 4 describes schematically, as a flowchart, the sequencing of the steps associated to the three tasks.

Fig. 4.

Flowchart of HiCo-MoG steps.

5.5. Correctness proof

We will provide some evidence related to the proposed group membership algorithm. The correctness of HiCo-MoG is ensured by proving that it satisfies the defined specification properties: Self inclusion.

This property requires a member of the group G to be present in any view it knows about. So, there is an initial view that is installed by all Mobile hosts that appear in it. Afterwards, modifications in group membership are carried out only under the condition that the mobile host which installs the new view belongs to it. In HiCo-MoG algorithm, when G is created in Task1, every group member $m_{i}$ installs the same initial view ${VM}_{i} .1$ . First, upon the discovery step, the initiator is included in the initial view. Mobile hosts intending to join G add their self to their view only when they want to join it. Then in Task2, the membership service (represented so far by the initiator) clearly sends to initial group members only those views including members that have sent a ConfirmGroup(G) message in Task1. After that in Task3, every mobile host receiving any other view, checks if it is the recent one. If so, while the consensus is executed immediately thereafter to agree on a new view, it will not be possible that a mobile node agree on a view without being included it. So, this property holds.

Initial View Event.

Among the characteristics of view-oriented group communication systems is that events which occur before the first view are not considered to be occurring in any views. The group membership service typically installs the initial view at the start-up time, and thus every sent or received message after that is considered as event of group communication and occurs in some views. In our case, members uses the group membership service to agree on the initial view as they do for any other view. This is accomplished in Task3.3 of HiCo-MoG when the first members joining the group receive $VM .1$

Local Monotonicity.

The sequence of views provided by every mobile host has a monotonically increasing sequence of view identifiers. Whenever the group composition is affected by any group membership events, the consensus protocol is called to agree on a new view with an identifier greater than the predecessor one. Since each member always receives distinct views as the decision of consensus, Local Monotonicity follows.

View Agreement.

Members providing the same views are said to have reached agreement on views. This property is assured by the agreement property of the HCD protocol with next view as proposal parameter (see HCD Algorithm [40]). At the end of Task1-Phase2 of HCD, a member can decide on a view by sending it to all other members. Upon any member receives it in Task2 corresponding to a Reliable Broadcast, the decision will be forwarded and all members will decide on the same view.

Membership Precision.

The system has the stable component as the failure detector $◇ C$ has the Global Stabilization Time (GST) to reach a stable state. The liveness property is the termination of HCD consensus protocol. This property ensures that the decided value is the most recent one. So, if S is a stable component after GST, all MHs in S will agree on the same view which is the most recent one. For the exchanged messages in S, the group membership semantics dictates that each message sent in a view is received in the same view. This problem arises especially during join or leave operations. In HiCo-MoG, after a possible occurrence of these operations, the consensus is called to agree on a new view. As we have supposed the virtual synchrony properties, every message that a member in S sent is received in the same view.

6. Results and discussion

HiCo-MoG is different from other group membership protocols. Its novelty lies in the use of a deterministic hierarchical consensus in group membership in large MANET. First, it ensures dynamic clustering (i.e. the clusterheads are updated in the case of failures or mobility, and any member can change its cluster and join another when it moves around the area of interest). Second, the used consensus is very adapted since it manages the mobility in order to accelerate its execution and so agree on new views when they are altered. Third, HiCo-MoG can serve as a base bloc for securing mobile group communications.

6.1. Contribution of HiCo-MoG

In MANETs, some criteria are known to be effective for any mobile group management. They mainly includes consistency, the mobility management model, clustering scheme, fault tolerance mechanism and scalability. In Table 2, we compare HiCo-MoG with the well known group membership protocols designed for wireless and mobile Ad Hoc networks. According to selected criteria, the comparison shows clearly the contribution of our method.

Table 2
Comparison with the well known solutions

Parakash and Baldoni (1998) [32] Roman et al. (2001) [34] Keidar et al. (2002) [27] Gutierrez-N. et al. (2014) [23] HiCo-MoG

Underlying based criteria for consistency Location of nodes Safe distance Network event mechanism for WAN Partial member connectivity Determination of hierarchical consensus

Detection of crashed nodes No Only link failures Yes No Yes

Mobility management Yes Yes No Yes Integrated with failure detector module

Consensus based No No No No Yes

The high availability of clusterheads (or leaders) No subdivision into sub-groups / Not treated Assumes fixed reliable servers / Not treated Yes

Replacement of clusterheads / / No / Yes

Application to large MANET No No Designed for WAN Yes Yes

	Parakash and Baldoni (1998) [32]	Roman et al. (2001) [34]	Keidar et al. (2002) [27]	Gutierrez-N. et al. (2014) [23]	HiCo-MoG
Underlying based criteria for consistency	Location of nodes	Safe distance	Network event mechanism for WAN	Partial member connectivity	Determination of hierarchical consensus
Detection of crashed nodes	No	Only link failures	Yes	No	Yes
Mobility management	Yes	Yes	No	Yes	Integrated with failure detector module
Consensus based	No	No	No	No	Yes
The high availability of clusterheads (or leaders)	No subdivision into sub-groups	/ Not treated	Assumes fixed reliable servers	/ Not treated	Yes
Replacement of clusterheads	/	/	No	/	Yes
Application to large MANET	No	No	Designed for WAN	Yes	Yes

6.2. Correctness of the consensus

Like any consensus protocol, it must be demonstrated that the validity, agreement and termination properties of the consensus are satisfied. We will demonstrate that these three properties are satisfied for HiCo-MoG protocol, as it is executed in association with the consensus protocol.

Theorem 1 (Validity).

If a mobile host decides a view v then v contains only initial views proposed by the mobile hosts.

Proof.
The clusterhead deciding in the consensus collects only the values proposed by the hosts in $◇ C : CH$ . Each clusterhead in this set collects either the values contained in the received ${leave}_{G}$ or ${join}_{G}$ messages from mobile hosts, or the values proposed by its local hosts. Therefore, the decided value v contains only the initial values of the $MH s$ in the group. Suppose that no mobile host is suspected and that $h_{k}$ is the only mobile host that want to leave the group G. So the group view will be changed by deleting $h_{k}$ from the current view and the remaining members must agree on the view v. While its clusterhead is correct after the GST, it will receive a message $J & L$ and will launch the consensus with an updated view without $h_{k}$ . The consensus will be performed with a decided view that is effectively proposed. At the end of the consensus, the decided view cannot be outside of the one proposed. □
Theorem 2 (Agreement).

Two mobile hosts do not decide differently.

Proof.
This property is fully insured by the consensus module. Therefore, it depends on the agreement property of the HCD protocol. A $MH$ only decides if its clusterhead receives the decision. In this case, the host $h_{k}$ adopts the decision of $◇ C : {clusterhead}_{k}$ . Thus, Theorem 2 is only valid if two clusterheads do not decide differently. Each clusterhead receives the decision of the deciding clusterhead. So all clusterheads in $◇ C : CH$ receive the same decision. Therefore, two hosts cannot decide differently. □
Lemma 1.
No collector can be blocked indefinitely in the collection of proposals.
Proof.
During the collection phase, each clusterhead collects estimates view from their local hosts. Since the communication channels are assumed to be reliable and depending on the properties of the failure detectors $◇ C$ , a $MH$ is either correct (and eventually participates) or suspected. Therefore, a correct clusterhead completes the execution of the collection phase. □
Lemma 2.
No clusterhead can be blocked indefinitely in the decision phase.
Proof.
When a decision is reached between the clusterheads, each clusterhead sends the decision to its local hosts. So, this phase ends. □
Theorem 3 (Termination).

Any correct mobile host decides after a finite time.

Proof.
A $MH$ decides whether the consensus protocol ends. This protocol can be considered to consist of two main phases: collection and delivery of the decision. According to Lemmas 1 and 2, the protocol ends if each of these two phases ends. Precisely, whatever the cause of a change of the group view, it is the clusterhead that will decide on the agreement on the new view. That is due to the property of $◇ C$ : after a stable time (GST) all correct hosts get the same stable $◇ C : CH$ and each correct host is associated with a correct clusterhead. There will be a time when a correct clusterhead becomes a coordinator in a given round. At this time, the coordinator will not be suspected by any other correct host. Hence, it will be able to impose its proposed new view and decides on it. All the correct hosts eventually decide due to reliable broadcast primitive, and the protocol ends. □

6.3. Discussion of security issue

Mobile Ad-Hoc networks are characterized by the frequent group membership change and unpredictable topology inducted by mobility of their hosts. This makes the application of some group key management protocols proposed for wired networks to this environment a very challenging. Various research efforts were carried out in order to adapt them to MANETs. Similar to group membership issue, some works in group key management are focused to study the possibility to distinguish the more adequate solutions to this environment. Even with the constraints of MANETs, the efficiency of these solutions are proven for small groups. For the most part of them, it’s still not easy to prove their efficiency when the number of group participants is important, thus are not scalable. To overcome with this problem, the subdivision of the whole large group into groups of moderate sizes (or clusters) is favoured. According to clustering architecture of HiCo-MoG, group membership can be restricted to nodes which trust each other. So, the group key can be carefully establishment with the guaranty of its confidentiality. The absence of a central authentication server in MANETs for generating the group key can be addressed by using a group key agreement [4]. Security functionality can be added in the attributes chosen for the group formation. The contributions of members are their public keys that can be sent with a ${Confirm}_{G}$ massage after receiving the ${Discovery}_{G}$ from the initiator. Then, the global group key can be derived by means of cryptography secure hash function, such as the one of [16]. The clusterheads are responsible in generating a group key based on their current locals keys and broadcasting it’s local hosts in each cluster. For the group key maintenance, upon the occurrence of any change in the clusterhead set or in members of any cluster, then corresponding local cluster key and the global group key will be updated within an auxiliary group key agreement scheme.

7. Conclusion

Group membership service is an important bloc in designing Group Communication Service (GCS). We have proposed HiCo-MoG, that is a new method for group management in MANETs using hierarchical consensus. The division of the entire group into sub-groups via $◇ C$ has simplified the design of reliable group membership service. For our knowledge, it is the first attempt of using a deterministic consensus in group membership in MANETs. This service can be very important basic bloc when developing solutions for secure group communications in MANET. As a future works, we envision to integrate the security services in group management and evaluate the hybrid group key management protocols using the proposed group management scheme in mobile Ad Hoc networks.

References

Amad,

Aissani,

Meddahi and

Saadi, Multi group key agreement mechanism for mobile P2P wireless networks, in: Proceedings CIIA 2011, Saida, Algeria, 2011.

André,

Rivière and

Waeselynck, A toolset for mobile systems testing, in: International Conference on Verification and Evaluation of Computer and Communication Systems, Springer, Cham, 2017, pp. 124–138. doi:10.1007/978-3-319-66176-6_9.

Asplund,

Lovhall and

Villani, Specification, implementation and verification of dynamic group membership for vehicle coordination, in: Dependable Computing (PRDC), 2017 IEEE 22nd Pacific Rim International Symposium, IEEE, 2017, pp. 321–328. doi:10.1109/PRDC.2017.57.

Augot,

Bhaskar,

Issarny and

Sacchetti, An efficient group key agreement protocol for Ad Hoc networks, in: Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks (WoWMOM) 2005.

Babaoglu,

Davoli and

Montresor, Group membership and view synchrony in partitionable asynchronous distributed systems: Specifications, Operating Systems Review 31(2) (1997), 11–22. doi:10.1145/250007.250010.

Bagchi, A distributed algorithm for ordered, atomic and simultaneous group communication, Future Generation Computer Systems 27 (2011), 466–475. doi:10.1016/j.future.2010.12.002.

Baldoni,

Helary and

Tucci-Piergiovanni, Group communication in Ad-Hoc networks: A few results and a case study, in: Proc. IEEE Int’l Conf. Pervasive Services (ICPS’05), 2005.

Basile,

Killijian and

Powell, A Survey of Dependability Issues in Mobile Wireless Networks, Technical Report, LAAS CNRS, Toulouse, France, 2003.

Benkaouha,

Abdelli,

Badache,

Ben-Othman and

Mokdad, Towards improving failure detection in mobile Ad Hoc networks, in: Global Communications Conference (GLOBECOM), IEEE 2015, pp. 1–6.

10.

Benzaid and

Badache, An optimal causal broadcast protocol in mobile dynamic groups, in: 2008 International Symposium on Parallel and Distributed Processing with Applications, 2008.

11.

Biggs,

Cooley,

Miller and

Whitsell, Group membership block chain, Google Patents (2018).

12.

Cachin,

Guerraoui and

Rodrigues, Introduction to Reliable and Secure Distributed Programming, Springer Science & Business Media, 2011.

13.

Chandra,

Hadzilacos and

Toueg, On the impossibility of group membership, in: Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing, PODC 1996, USA, ACM, 1996, pp. 322–330.

14.

Chandra,

Hadzilacos and

Toueg, The weakest failure detector for solving consensus, J. of ACM 43(4) (1996). doi:10.1145/234533.234549.

15.

Chandra and

Toueg, Unreliable failure detectors for reliable distributed systems, Journal of ACM 43(2) (1996), 225–267. doi:10.1145/226643.226647.

16.

Cho,

Chen and

Wang, Performance characteristics of region-based group key management in mobile Ad Hoc networks, in: Proceedings of the IEEE International Conference on Sensor Networks, Ubiquitous, and Trustworthy Computing (SUTC’06) 2006.

17.

G.V.

Chokler,

Keidar and

Vitenberg, Group communication specifications: A comprehensive study, ACM Computing Surveys 33(4) (2001), 1–43.

18.

A.R.D.

De Vit,

Marcon and

R.C.

Nunes, Signal strength as support to mobility detection on failure detectors, in: Proceedings of the Symposium on Applied Computing, ACM, 2017, pp. 647–650.

19.

Evropeytsev,

E.L.

Domínguez,

S.E.P.

Hernandez,

M.A.L.

Trinidad and

J.R.P.

Cruz, An efficient causal group communication protocol for P2P hierarchical overlay networks, Journal of Parallel and Distributed Computing, Elsevier 102 (2017), 149–162. doi:10.1016/j.jpdc.2016.12.007.

20.

Fischer,

Lynch and

Peterson, Impossibility of distributed consensus with one faut process, Journal of the ACM 32(2) (1985), 374–382. doi:10.1145/3149.214121.

21.

Gómez-Calzado, Contributions on Agreement in Dynamic Distributed Systems, Ph.D. Thesis, Universide del País Vasco-Euskal Herriko Unibertsitatea, Leioa, Vizcaya, Spain, 2015.

22.

Guerraoui,

A.P.

Kermarrec and

M.S.

Dragos-Adrian, Atum: Scalable group communication using volatile groups, in: Proceedings of the 17th International Middleware Conference, ACM, 2016, p. 19.

23.

Gutierrez-Nolasco,

Venkatasubramanian,

Stehr and

Talcott, Tailoring consistency in group membership for mobile networks, Future Generation Computer Systems 31 (2014), 134–146. doi:10.1016/j.future.2013.06.014.

24.

Huang,

Julien and

G.C.

Roman, Relying on safe distance to achieve strong partitionable group membership in Ad Hoc networks, IEEE Transactions on Mobile Computing 3(2) (2004), 192–205. doi:10.1109/TMC.2004.14.

25.

Hurfin,

Macêdo,

Raynal and

Tronel, A general framework to solve agreement problems, in: Proc. 18th IEEE Symp. on Reliable Distributed Systems – SRDS, 1999, pp. 56–65. doi:10.1109/RELDIS.1999.805083.

26.

Hurfin,

Mostefaoui and

Raynal, A versatile family of consensus protocols based on Chandra–Toueg’s unreliable failure detectors, IEEE Trans. Computers 51(4) (2002), 395–408. doi:10.1109/12.995450.

27.

Keidar,

Sussman,

Marzullo and

Dolev, Moshe: A group membership service for WANs, ACM Transactions on Computer Systems 20(3) (2002), 1–48. doi:10.1145/566340.566341.

28.

Lim and

Conan, Partitionable group membership for mobile ad hoc networks, Journal of Parallel and Distributed Computing 74(8) (2014), 2708–2721. doi:10.1016/j.jpdc.2014.03.003.

29.

Liu,

Sacchetti,

Sailhan and

Issarny, Group management for mobile ad hoc networks: Design, implementation and experiment, in: Proceedings of the 6th International Conference on Mobile Data Management, ACM, 2005, pp. 192–199. doi:10.1145/1071246.1071276.

30.

Loo,

J.L.

Mauri and

J.H.

Ortiz, Mobile Ad Hoc Networks: Current Status and Future Trends, CRC Press, 2016.

31.

Macedo,

Freitas and

Santo de S‘a, Enhancing group communication with self-manageable behavior, J. Parallel Distrib. Comput. 73 (2013), 420–433. doi:10.1016/j.jpdc.2012.12.005.

32.

Prakash and

Baldoni, Architecture for group communication in mobile systems, in: Reliable Distributed Systems, 1998. Proceedings. Seventeenth IEEE Symposium on, IEEE, 1998, pp. 235–242.

33.

Qiu,

Chen,

Li,

Qiao and

Fu, Heterogeneous Ad Hoc networks: Architectures, advances and challenges, Ad Hoc Networks 55 (2017), 143–152. doi:10.1016/j.adhoc.2016.11.001.

34.

G.C.

Roman,

Huang and

Hazemi, Consistent group membership in Ad Hoc networks, in: Proceedings of the 23rd International Conference on Software Engineering, IEEE Computer Society, 2011, pp. 381–388.

35.

Schiper, Failure detection vs group membership in fault-tolerant distributed systems: Hidden trade-offs, in: PAPM-PROBMIV’02: Proceedings of the Second Joint International Workshop on Process Algebra and Probabilistic Methods, Performance Modeling and Verification, Springer-Verlag, London, UK, 2002, pp. 1–15.

36.

Schiper, Group communication: Where are we today and future challenges, in: Proc. 4th IEEE NCA, Washington, DC, USA, 2004.

37.

Seba,

Bouabdallah and

Badache, Increasing the robustness of initial key agreement using failure detectors, GLOBECOM IEEE (2003).

38.

Shin,

Guan and

B.Y.

Choi, A dynamic location management service for group applications in cellular networks, Telecommunication Systems 65(3) (2017), 479–495. doi:10.1007/s11235-016-0239-2.

39.

Tengroth and

Vong, Evaluation of a synchronous leader-based group membership protocol (Dissertation), 2018. Retrieved from http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-144842.

40.

Wu,

Cao and

Raynal, Eventual clusterer: A modular approach to designing hierarchical consensus protocols in MANETs, IEEE Trans. on Parallel and Distributed Systems 20(6) (2009), 753–765. doi:10.1109/TPDS.2008.266.

41.

Wu,

Cao,

Yang and

Raynal, Design and performance evaluation of efficient consensus protocols for mobile Ad Hoc networks, IEEE Trans. Computers 56(8) (2007), 1055–1070. doi:10.1109/TC.2007.1053.

${Join}_{G}$	message sent by a $MH$ to its neighbors informing him about its intention to join the group G
${Leave}_{G}$	message sent by a $MH$ to its clusterHead informing him about its intention to leave the group G
J	the set of members that have sent a ${Join}_{G}$
L	the set of members that have sent a ${Leave}_{G}$
$J & L$	the merged message containing the two sets J and L
${Discovery}_{G}$	message sent by the initiator to inform the mobile hosts about its intention to create the group G
${Confirm}_{G}$	message sent to the initiator informing him about its intention to join the group G
$MH$	a mobile host (a node)
${VM}_{i}$	the view installed by ${MH}_{i}$ , it’s made of two fields: ${VM}_{i} . id$ (its identity) and ${VM}_{i} . members$ (its composition)
$◇ C . {CH}_{i}$	the actual list of designed clusterheads, it’s the output of the failure detector $◇ C$ associated to ${MH}_{i}$
$◇ C . {clusterhead}_{i}$	the actual clusterhead of ${MH}_{i}$ , it’s the output of $◇ C$
$HCD (VM)$	the call of the HCD protocol with $VM$ as the proposed input parameter
$send (m)$	primitive that sends the message m