Resilience of Infrastructure Networks Byzantine Consensus, Interdependencies, and Optimisation in Sparse Networks
MetadataShow full item record
The growing dependence on critical infrastructure systems demands highly available systems that provide secure, resilient, and efficient services, even in the presence of malicious attacks. This thesis investigates the problem of Byzantine consensus, interdependencies, and optimisation in infrastructure systems (e.g., smart grids and micro-grids). It consists of the following three main parts. The first part focuses on investigating Byzantine consensus in sparse networks. Consensus problems and their efficient solution are a fundamental problem in distributed systems, particularly in the presence of Byzantine faults. Whilst asynchronous message passing represents an interesting network model, the fundamental result of Fischer, Lynch, and Paterson showed the impossibility of deterministic algorithms even for single faults, requiring the use of randomisation as first proposed by Ben-Or. Existing results have implicitly assumed full connectivity, but we argue that the case of noncomplete graphs represents a particularly interesting case when studying the feasibility and efficiency of such consensus problems that has received limited scrutiny thus far. Such graph structures are, however, ubiquitous in many networks requiring both low overall latency and reliable signalling as in the case of reconciling sensor data in electrical power networks. One of the core benefits of such an approach is the ability to actively rely on redundant sensors in large networks both for fault detection and potential adversarial action where real-time behaviour must not be jeopardised. It is therefore critical to minimise the message complexity of any such consensus algorithm. In this part, we study the problem of binary consensus problem over non-complete graphs and describe algorithms which not only yield the desired primary result, but also achieve this with the stronger constraint of messages by extending Correia et al. variant of Ben-Or’s algorithm. The main contribution is the development of an algorithm which explicitly utilises the network structure to gain efficiency over a simple randomised algorithm, also allowing the identification of possible additional edges in the graph to satisfy redundancy requirements. The second part targets at understanding the impact of interdependencies in sparse networks. The interdependence of infrastructure networks, particularly of information and telecommunication networks and systems and electrical power networks has been studied intensively employing a number of different methods ranging from semi-qualitative Leontief models via percolation models and related approaches from statistical physics to agent and graph-theoretical models. This work is based on the latter approach and studies the structures arising from incomplete joining of two power-law networks. Both ICT and power networks are artificial networks, but a number of studies demonstrate that such networks generally exhibit scale-free properties and can be described with high accuracy by power-law degree sequence graphs. A well-known result is that the robustness of such networks to random failures and intentional attack differs considerably, with high levels of vulnerability to targeted attacks. However, differences in robustness exist based on the exact degree sequence. Dependencies between two or more such networks can result in both dependency paths, where the length of paths and the existence of vertex-and edge-disjoint paths can inform mitigation mechanisms; more importantly, however, cycles arising indicate the existence of interdependencies that may be more difficult to recover from or mitigate. This has been studied previously for both simple graphs and for flows; however, we argue that particularly for the case of interdependencies between power and ICT networks in smart grid environments, this relation between the graphs is itself not static. We consider the existence, addition, or removal of dependencies in the form of sparse random graphs resulting in the creation of interdependence cycles. The diameter of such cycles can serve as a strong indicator of the vulnerability of the overall network as it is indicative of the attack surface of the network. The introduction of additional edges in the graph, indicating information flows in the smart grid, can hence reduce vulnerabilities, thus the efficient discovery of such structures for a given graph is of particular interest. The third part focuses on developing a set of distributed algorithms for demand management in smart micro-grids. Demand management is the key to the efficiency and reliability of smart grids. Even more than in smart grid environments, the effective and reliable operation of micro-grids with limited ability to compensate for fluctuating demand by averaging over a large number of loads and relying on statistical models, require microgrids to rely on demand management. We argue that this can and should be augmented by explicit demand projection and to integrate the demand profile for loads into the balancing and demand management mechanism. For micro-grids in disadvantaged environments, this cannot rely on the integrity of loads or centralised building energy managers and smart meters; instead, demand projection and communication must rely on distributed, opportunistically employed devices with limited trustworthiness. Specifically, this part develops two distributed algorithms to project power demand and optimise the power consumption scheduling in micro-grids. The first one employs a distributed algorithm based on approximate consensus problem over non-complete graphs using random geometric graphs, and describes an algorithm that enables a group of devices to agree on a way to use power (project demand) that are different from each other within an arbitrary predefined value in the presence of non-cooperating devices. The second one develops a decentralised power consumption scheduling algorithm to manage the scheduling of appliances of consumers in a distributed way; in particular, alternating direction method of multipliers(ADMM) is employed to solve the power consumption scheduling optimisation problem in a decentralised manner. Additionally, we show that false data injection attacks can be provoked by compromising parts of the communication infrastructure or a set of computing devices. In this case, the algorithm fails to converge to an optimum or converges toward a value that lends the attacker an advantage, and impacts the scheduling scheme negatively.