| dc.description.abstract | 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. | nb_NO |
