Enabling Robust and Efficient Distributed Computation in Dynamic Peer-to-Peer Networks

Motivated by the need for designing efficient and robust fully-distributed computation in highly dynamic networks such as Peer-to-Peer (P2P) networks, we study distributed protocols for constructing and maintaining dynamic network topologies with good expansion properties. Our goal is to maintain a sparse (bounded degree) expander topology despite heavy {\em churn} (i.e., nodes joining and leaving the network continuously over time). We assume that the churn is controlled by an adversary that has complete knowledge and control of what nodes join and leave and at what time and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Our main contribution is a randomized distributed protocol that guarantees with high probability the maintenance of a {\em constant} degree graph with {\em high expansion} even under {\em continuous high adversarial} churn. Our protocol can tolerate a churn rate of up to $O(n/\poly\log(n))$ per round (where $n$ is the stable network size). Our protocol is efficient, lightweight, and scalable, and it incurs only $O(\poly\log(n))$ overhead for topology maintenance: only polylogarithmic (in $n$) bits needs to be processed and sent by each node per round and any node's computation cost per round is also polylogarithmic. The given protocol is a fundamental ingredient that is needed for the design of efficient fully-distributed algorithms for solving fundamental distributed computing problems such as agreement, leader election, search, and storage in highly dynamic P2P networks and enables fast and scalable algorithms for these problems that can tolerate a large amount of churn.

Fast Byzantine Leader Election in Dynamic Networks

We study the fundamental Byzantine leader election problem in dynamic networks where the topology can change from round to round and nodes can also experience heavy {\em churn} (i.e., nodes can join and leave the network continuously over time). We assume the full information model where the Byzantine nodes have complete knowledge about the entire state of the network at every round (including random choices made by all the nodes), have unbounded computational power and can deviate arbitrarily from the protocol. The churn is controlled by an adversary that has complete knowledge and control over which nodes join and leave and at what times and also may rewire the topology in every round and has unlimited computational power, but is oblivious to the random choices made by the algorithm. Our main contribution is an $O(\log^3 n)$ round algorithm that achieves Byzantine leader election under the presence of up to $O({n}^{1/2 - \epsilon})$ Byzantine nodes (for a small constant $\epsilon > 0$) and a churn of up to \\$O(\sqrt{n}/\poly\log(n))$ nodes per round (where $n$ is the stable network size).The algorithm elects a leader with probability at least $1-n^{-\Omega(1)}$ and guarantees that it is an honest node with probability at least $1-n^{-\Omega(1)}$; assuming the algorithm succeeds, the leader's identity will be known to a $1-o(1)$ fraction of the honest nodes. Our algorithm is fully-distributed, lightweight, and is simple to implement. It is also scalable, as it runs in polylogarithmic (in $n$) time and requires nodes to send and receive messages of only polylogarithmic size per round.To the best of our knowledge, our algorithm is the first scalable solution for Byzantine leader election in a dynamic network with a high rate of churn; our protocol can also be used to solve Byzantine agreement in a straightforward way.We also show how to implement an (almost-everywhere) public coin with constant bias in a dynamic network with Byzantine nodes and provide a mechanism for enabling honest nodes to store information reliably in the network, which might be of independent interest.

Detection of Bridge Dynamic Parameters using an Instrumented Vehicle

Highway structures such as bridges are subject to continuous degradation primarily due to ageing and environmental factors. A rational transport policy requires the monitoring of this transport infrastructure to provide adequate maintenance and guarantee the required levels of transport service and safety. In Europe, this is now a legal requirement - a European Directive requires all member states of the European Union to implement a Bridge Management System. However, the process is expensive, requiring the installation of sensing equipment and data acquisition electronics on the bridge. This paper investigates the use of an instrumented vehicle fitted with accelerometers on its axles to monitor the dynamic behaviour of bridges as an indicator of its structural condition. This approach eliminates the need for any on-site installation of measurement equipment. A simplified half-car vehicle-bridge interaction model is used in theoretical simulations to test the possibility of extracting the dynamic parameters of the bridge from the spectra of the vehicle accelerations. The effect of vehicle speed, vehicle mass and bridge span length on the detection of the bridge dynamic parameters are investigated. The algorithm is highly sensitive to the condition of the road profile and simulations are carried out for both smooth and rough profiles

A Constrained Optimization Approach to Dynamic State Estimation for Power Systems Including PMU and Missing Measurements.

In this brief, a hybrid filter algorithm is developed to deal with the state estimation (SE) problem for power systems by taking into account the impact from the phasor measurement units (PMUs). Our aim is to include PMU measurements when designing the dynamic state estimators for power systems with traditional measurements. Also, as data dropouts inevitably occur in the transmission channels of traditional measurements from the meters to the control center, the missing measurement phenomenon is also tackled in the state estimator design. In the framework of extended Kalman filter (EKF) algorithm, the PMU measurements are treated as inequality constraints on the states with the aid of the statistical criterion, and then the addressed SE problem becomes a constrained optimization one based on the probability-maximization method. The resulting constrained optimization problem is then solved using the particle swarm optimization algorithm together with the penalty function approach. The proposed algorithm is applied to estimate the states of the power systems with both traditional and PMU measurements in the presence of probabilistic data missing phenomenon. Extensive simulations are carried out on the IEEE 14-bus test system and it is shown that the proposed algorithm gives much improved estimation performances over the traditional EKF method.

Design and Flux-Weakening Control of an Interior Permanent Magnet Synchronous Motor for Electric Vehicles

Permanent magnet synchronous motors (PMSMs) provide a competitive technology for EV traction drives owing to their high power density and high efficiency. In this paper, three types of interior PMSMs with different PM arrangements are modeled by the finite element method (FEM). For a given amount of permanent magnet materials, the V-shape interior PMSM is found better than the U-shape and the conventional rotor topologies for EV traction drives. Then the V-shape interior PMSM is further analyzed with the effects of stator slot opening and the permanent magnet pole chamfering on cogging torque and output torque performance. A vector-controlled flux-weakening method is developed and simulated in Matlab to expand the motor speed range for EV drive system. The results show good dynamic and steady-state performance with a capability of expanding speed up to four times of the rated. A prototype of the V-shape interior PMSM is also manufactured and tested to validate the numerical models built by the FEM.