The eventual clusterer oracle and its application to consensus in MANETs

This paper studies the design of hierarchical consensus protocols for mobile ad hoc networks. A two-layer hierarchy is imposed on the mobile hosts by grouping them into clusters, each with a clusterhead. The messages from and to the hosts in the same cluster are merged/unmerged by the clusterhead so as to reduce the message cost and improve the scalability. We adopt a modular method in the design, separating clustering from achieving consensus using the clusters. The clustering function, named eventual clusterer (denoted as lozenge, openC), is designed to construct a cluster-based hierarchy over the mobile hosts in the network. Since OC provides the fault tolerant clustering function transparently, it can be used as a new oracle (i.e. an abstract tool to provide some kind of information about the state of the system) for the design of hierarchical consensus protocols. Based on lozenge, openC, we design a new consensus protocol, which can significantly reduce the message cost of achieving consensu. We also propose an implementation of the OC oracle based on the failure detector lozenge, openS.