Skip to main content

Surviving Network Partitioning in Distributed Wireless Systems

Researcher: Priya Narasimhan

Research Area: Survivable Distributed Systems

Abstract

Surviving Network Partitioning in Distributed Wireless Systems

Many distributed applications often require data to be consistent across multiple, distributed nodes that are connected by a network. These applications typically achieve data consistency by ensuring that updates to the application’s state are done by all the nodes in the same order. Unfortunately, link failures in the underlying network can cause a single system to split into multiple disjoint, disconnected partitions. As a result of such network-partitioning faults, nodes within a partition can communicate with each other, but there is no communication across nodes in different partitions. If the application is allowed to continue to operate in all of the disjoint partitions, the distributed application’s state might become inconsistent, thereby leading to difficulties when the network remerges subsequently. Current strategies to handle the network-partition and the network-remerge problem adopt the extreme approach of allowing only one of the partitions to survive, while the nodes and application processes in the other partitions are forcibly shut down (called primary component approach); manual intervention is often required, when the network-partition heals, to re-introduce the killed processes and nodes back into the distributed system. The primary component strategy is infeasible and impractical for large networks of nodes, and also for distributed systems where a (potentially non-trivial) number of nodes cannot simply shut down and cease operation. For instance, in the embedded distributed network of nodes inside an automotive control system, shutting down half or more of the nodes within the car, while the car is on the road, is neither safe nor practical. This problem is exacerbated in wireless systems where node mobility can cause the network to partition and remerge several times. In such a dynamic environment, manual reconciliation of states may not be feasible due to the high frequency with which the network can partition and remerge while primary component approach can significantly degrade the application’s performance by reducing the number of nodes available to the application. Therefore, there is an urgent need to develop techniques to effectively cope with network partitioning failures before distributed applications can be satisfactorily used in mobile networks.

Recognizing the infeasibility of this approach for real-world applications that can afford neither downtime nor manual intervention, this project aims at developing key building-blocks that can be exploited to support partition-tolerant distributed systems, along with mechanisms to facilitate a distributed application’s state consistency during remerging. The proposed approach aims to address the challenges of network partitioning through a combination of a static program-analysis element, along with distributed, run-time fault-tolerance and logging infrastructures to address the challenges behind surviving network partitioning in a distributed system.

Proposed Approach

The intention of this project is to develop key building-blocks that can be exploited to support partition-tolerant infrastructures and to facilitate replica consistency during remerging. With these additional mechanisms, we could also sustain continuous, albeit degraded, operation in each partition of a partitioned system, and could facilitate remerging and recovery when the partition heals. This project proposes to address the challenges of network partitioning by a combination of

  • Static program analysis component. Static analysis of the application code is used to determine what action is to be taken for the different state variables in case of a network-partition. The idea here is that the static program analysis should be able to determine state variables that can be shared amongst the partitioned components and how to merge the shared components back. For variables that can be shared amongst the different partitions, strategies need to be developed on how to share the variable (like, dividing the state variable’s pre-partition value equally amongst all partitions, using the pre-partition value in all partitions, etc.) and how to merge the variable’s value in multiple partitions to generate its value in the merged partition (like, adding the state variable’s value in all partition to generate the merged value, taking the maximum of the state variable’s value in all partitions, etc.). Since the application’s state is shared, it is possible that the applications performance may be degraded during the network-partitioning phase. But the application can once again perform to its full potential as soon as the different partitions are merged back into a single partition. We may not be able to ensure that every state variable can be shared and updated amongst the different components without causing inconsistencies. In such a case, inputs that cause these variables to change in the different components might have to be buffered till the partition is healed. Thus, the static program analysis component is an application dependent module which allows the application to be made partition-tolerant by allowing partition/merge strategies to be annotated for the different variables in the application’s state. One objective of this project is to facilitate automatic code annotation by adding extensions in the compiler that allow a choice of commonly used strategies to handle partitioning/merging of application’s state variables.
  • Dynamic component. This component is responsible for detecting the occurrence of network partitions and deter- mining how many replicas are there in each partition. The outputs of this dynamic component are fed as inputs to the static component to ensure sharing the state in such a way that there are no inconsistencies when the partitions are healed. The significant problem solved by the dynamic component is to distinguish between network partitioning faults from crash failures and other kind of faults. Otherwise, if a crash failure is falsely detected as a network partitioning fault, the application’s performance may degrade due to the sharing of state variables. In wireless systems, we propose to use the strength of the signal received at each node to construct the topology of the wireless network and to predict the occurrence of network partitioning failures. Other responsibilities of the dynamic component are to bridge the partitions quickly by not only predicting the occurrence of network partitioning failures but also through the use of self-organization protocols and by using flooding or store-and-forward mechanisms to transmit messages between partitioned components.

Thus, the challenges addressed by our proposed approach for building partition-tolerant distributed systems are:

  • Differentiating a network-partitioning fault from any other kind of communication fault, such as the loss of a message, or the crash of a single node in the system,
  • Recognizing the onset of a network-remerge, and differentiating it from the introduction of a new node,
  • Categorizing the different kinds of state inside a distributed application, and recognizing which kinds of state are partition-tolerant and which are not,
  • Developing mechanisms to handle partition-intolerant kinds of state inside the distributed application,
  • Reconciling divergent states in partitions upon the onset of a network-remerge,
  • Handling situations where partitions sub-partition further, and remerge in unexpected ways, i.e., when the chain of network-remerges do not following the history of network-partitions, and
  • Most important of all, developing a body of understanding that allows us to build partition-tolerant and remerge-friendly distributed applications that require no manual intervention at either partition/remerge time, and that do not require aborting/halting any of the nodes in the system.

One of the problems with the current state-of-the-art techniques to handle network partitioning is that the applications performance can suffer not only during the partitioning phase (in non-primary partitions) but also after the network partitioning has been healed (since components in the non-primary partitions have been forced shut). Our approach allows the application to perform to its full potential once the partitions have healed by allowing nodes in all components to continue operating. This is advantageous in mobile systems, where the network partitioning and remerging occurs very frequently.