Sublinear Bounds for Randomized Leader Election

This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O(1) rounds and (with high probability) takes only O(n-vlog3/2n) messages to elect a unique leader (with high probability). This algorithm is then extended to solve leader election on any connected non-bipartiten-node graph G in O(t(G)) time and O(t(G)n-vlog3/2n) messages, where t(G) is the mixing time of a random walk on G. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficientdeterministic leader election algorithms. Finally, an almost-tight lower bound is presented for randomized leader election, showing that O(n-v) messages are needed for any O(1) time leader election algorithm which succeeds with high probability. It is also shown that O(n 1/3) messages are needed by any leader election algorithm that succeeds with high probability, regardless of the number of the rounds. We view our results as a step towards understanding the randomized complexity of leader election in distributed networks.

Context-Aware Body Area Networks (CABAN) for interactive smart environments:Interference characterization

Body Area Networks are unique in that the large-scale mobility of users allows the network itself to travel across a diverse range of operating domains or even to enter new and unknown environments. This network mobility is unlike node mobility in that sensed changes in inter-network interference level may be used to identify opportunities for intelligent inter-networking, for example, by merging or splitting from other networks, thus providing an extra degree of freedom. This paper introduces the concept of context-aware bodynets for interactive environments using inter-network interference sensing. New ideas are explored at both the physical and link layers with an investigation based on a 'smart' office environment. A series of carefully controlled measurements of the mesh interconnectivity both within and between an ambulatory body area network and a stationary desk-based network were performed using 2.45 GHz nodes. Received signal strength and carrier to interference ratio time series for selected node to node links are presented. The results provide an insight into the potential interference between the mobile and static networks and highlight the possibility for automatic identification of network merging and splitting opportunities. © 2010 ACM.

Xheal: A localized self-healing algorithm using expanders

We consider the problem of self-healing in reconfigurable networks e.g., peer-to-peer and wireless mesh networks. For such networks under repeated attack by an omniscient adversary, we propose a fully distributed algorithm, Xheal, that maintains good expansion and spectral properties of the network, while keeping the network connected. Moreover, Xheal does this while allowing only low stretch and degree increase per node. The algorithm heals global properties like expansion and stretch while only doing local changes and using only local information. We also provide bounds on the second smallest eigenvalue of the Laplacian which captures key properties such as mixing time, conductance, congestion in routing etc. Xheal has low amortized latency and bandwidth requirements. Our work improves over the self-healing algorithms Forgiving tree [PODC 2008] andForgiving graph [PODC 2009] in that we are able to give guarantees on degree and stretch, while at the same time preserving the expansion and spectral properties of the network.

Dense subgraphs on dynamic networks

In distributed networks, it is often useful for the nodes to be aware of dense subgraphs, e.g., such a dense subgraph could reveal dense substructures in otherwise sparse graphs (e.g. the World Wide Web or social networks); these might reveal community clusters or dense regions for possibly maintaining good communication infrastructure. In this work, we address the problem of self-awareness of nodes in a dynamic network with regards to graph density, i.e., we give distributed algorithms for maintaining dense subgraphs that the member nodes are aware of. The only knowledge that the nodes need is that of the dynamic diameter D, i.e., the maximum number of rounds it takes for a message to traverse the dynamic network. For our work, we consider a model where the number of nodes are fixed, but a powerful adversary can add or remove a limited number of edges from the network at each time step. The communication is by broadcast only and follows the CONGEST model. Our algorithms are continuously executed on the network, and at any time (after some initialization) each node will be aware if it is part (or not) of a particular dense subgraph. We give algorithms that (2 + e)-approximate the densest subgraph and (3 + e)-approximate the at-least-k-densest subgraph (for a given parameter k). Our algorithms work for a wide range of parameter values and run in O(D log n) time. Further, a special case of our results also gives the first fully decentralized approximation algorithms for densest and at-least-k-densest subgraph problems for static distributed graphs. © 2012 Springer-Verlag.

The forgiving tree: a self-healing distributed data structure

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that the following process continues for up to n rounds where n is the total number of nodes initially in the network: the adversary deletesan arbitrary node from the network, then the network responds by quickly adding a small number of new edges.

We present a distributed data structure that ensures two key properties. First, the diameter of the network is never more than O(log Delta) times its original diameter, where Delta is the maximum degree of the network initially. We note that for many peer-to-peer systems, Delta is polylogarithmic, so the diameter increase would be a O(loglog n) multiplicative factor. Second, the degree of any node never increases by more than 3 over its original degree. Our data structure is fully distributed, has O(1) latency per round and requires each node to send and receive O(1) messages per round. The data structure requires an initial setup phase that has latency equal to the diameter of the original network, and requires, with high probability, each node v to send O(log n) messages along every edge incident to v. Our approach is orthogonal and complementary to traditional topology-based approaches to defending against attack.

Picking up the Pieces: Self-Healing in reconfigurable networks

We consider the problem of self-healing in networks that are reconfigurable in the sense that they can change their topology during an attack. Our goal is to maintain connectivity in these networks, even in the presence of repeated adversarial node deletion, by carefully adding edges after each attack. We present a new algorithm, DASH, that provably ensures that: 1) the network stays connected even if an adversary deletes up to all nodes in the network; and 2) no node ever increases its degree by more than 2 log n, where n is the number of nodes initially in the network. DASH is fully distributed; adds new edges only among neighbors of deleted nodes; and has average latency and bandwidth costs that are at most logarithmic in n. DASH has these properties irrespective of the topology of the initial network, and is thus orthogonal and complementary to traditional topology- based approaches to defending against attack. We also prove lower-bounds showing that DASH is asymptotically optimal in terms of minimizing maximum degree increase over multiple attacks. Finally, we present empirical results on power-law graphs that show that DASH performs well in practice, and that it significantly outperforms naive algorithms in reducing maximum degree increase.

Algorithms for Self-Healing Networks

Many modern networks are \emph{reconfigurable}, in the sense that the topology of the network can be changed by the nodes in the network. For example, peer-to-peer, wireless and ad-hoc networks are reconfigurable. More generally, many social networks, such as a company's organizational chart; infrastructure networks, such as an airline's transportation network; and biological networks, such as the human brain, are also reconfigurable. Modern reconfigurable networks have a complexity unprecedented in the history of engineering, resembling more a dynamic and evolving living animal rather than a structure of steel designed from a blueprint. Unfortunately, our mathematical and algorithmic tools have not yet developed enough to handle this complexity and fully exploit the flexibility of these networks. We believe that it is no longer possible to build networks that are scalable and never have node failures. Instead, these networks should be able to admit small, and maybe, periodic failures and still recover like skin heals from a cut. This process, where the network can recover itself by maintaining key invariants in response to attack by a powerful adversary is what we call \emph{self-healing}. Here, we present several fast and provably good distributed algorithms for self-healing in reconfigurable dynamic networks. Each of these algorithms have different properties, a different set of gaurantees and limitations. We also discuss future directions and theoretical questions we would like to answer. %in the final dissertation that this document is proposed to lead to.

Brief announcement: Maintaining large dense subgraphs on dynamic networks

In distributed networks, some groups of nodes may have more inter-connections, perhaps due to their larger bandwidth availability or communication requirements. In many scenarios, it may be useful for the nodes to know if they form part of a dense subgraph, e.g., such a dense subgraph could form a high bandwidth backbone for the network. In this work, we address the problem of self-awareness of nodes in a dynamic network with regards to graph density, i.e., we give distributed algorithms for maintaining dense subgraphs (subgraphs that the member nodes are aware of). The only knowledge that the nodes need is that of the dynamic diameter D, i.e., the maximum number of rounds it takes for a message to traverse the dynamic network. For our work, we consider a model where the number of nodes are fixed, but a powerful adversary can add or remove a limited number of edges from the network at each time step. The communication is by broadcast only and follows the CONGEST model in the sense that only messages of O(log n) size are permitted, where n is the number of nodes in the network. Our algorithms are continuously executed on the network, and at any time (after some initialization) each node will be aware if it is part (or not) of a particular dense subgraph. We give algorithms that approximate both the densest subgraph, i.e., the subgraph of the highest density in the network, and the at-least-k-densest subgraph (for a given parameter k), i.e., the densest subgraph of size at least k. We give a (2 + e)-approximation algorithm for the densest subgraph problem. The at-least-k-densest subgraph is known to be NP-hard for the general case in the centralized setting and the best known algorithm gives a 2-approximation. We present an algorithm that maintains a (3+e)-approximation in our distributed, dynamic setting. Our algorithms run in O(Dlog n) time. © 2012 Authors.

The Forgiving Graph:A distributed data structure for low stretch under adversarial attack

We consider the problem of self-healing in peer-to-peer networks that are under repeated attack by an omniscient adversary. We assume that, over a sequence of rounds, an adversary either inserts a node with arbitrary connections or deletes an arbitrary node from the network. The network responds to each such change by quick "repairs," which consist of adding or deleting a small number of edges. These repairs essentially preserve closeness of nodes after adversarial deletions,without increasing node degrees by too much, in the following sense. At any point in the algorithm, nodes v and w whose distance would have been - in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most - log n in the actual graph, where n is the total number of vertices seen so far. Similarly, at any point, a node v whose degreewould have been d in the graph with adversarial insertions only, will have degree at most 3d in the actual graph. Our distributed data structure, which we call the Forgiving Graph, has low latency and bandwidth requirements. The Forgiving Graph improves on the Forgiving Tree distributed data structure from Hayes et al. (2008) in the following ways: 1) it ensures low stretch over all pairs of nodes, while the Forgiving Tree only ensures low diameter increase; 2) it handles both node insertions and deletions, while the Forgiving Tree only handles deletions; 3) it requires only a very simple and minimal initialization phase, while the Forgiving Tree initially requires construction of a spanning tree of the network. © Springer-Verlag 2012.

Reconfigurable Architectures for Network Processing

An overview of research on reconfigurable architectures for network processing applications within the Institute of Electronics, Communications and Information Technology (ECIT) is presented. Three key network processing topics, namely node throughput, Quality of Service (QoS) and security are examined where custom reconfigurability allows network nodes to adapt to fluctuating network traffic and customer demands. Various architectural possibilities have been investigated in order to explore the options and tradeoffs available when using reconfigurability for packet/frame processing, packet-scheduling and data encryption/decryption. This research has shown there is no common approach that can be applied. Rather the methodologies used and the cost-benefits for incorporation of reconfigurability depend on each of the functions considered, for example being well suited to encryption/decryption but not packet/frame processing. © 2005 IEEE.

Improvement in clinical step and shoot intensity modulated radiation therapy delivery accuracy on an integrated linear accelerator control system

Purpose: The dose delivery accuracy of 30 clinical step and shoot intensity modulated radiation therapy plans was investigated using the single integrated multileaf collimator controller of the Varian Truebeam linear accelerator (linac) (Varian Medical Systems, Palo Alto, CA) and compared with the dose delivery accuracy on a previous generation Varian 2100CD C-Series linac.

Methods and Materials: Ten prostate, 10 prostate and pelvic node, and 10 head-and-neck cases were investigated in this study. Dose delivery accuracy on each linac was assessed using Farmer ionization chamber point dose measurements, 2-dimensional planar ionization chamber array measurements, and the corresponding Varian dynamic log files. Absolute point dose measurements, fluence delivery accuracy, leaf position accuracy, and the overshoot effect were assessed for each plan.

Results: Absolute point dose delivery accuracy increased by 1.5% on the Truebeam compared with the 2100CD linac. No improvement in fluence delivery accuracy between the linacs, at a gamma criterion of 3%/3 mm was measured using the 2-dimensional ionization chamber array, with median (interquartile range) gamma passing rates of 98.99% (97.70%-99.72%) and 99.28% (98.26%-99.75%) for the Truebeam and 2100CD linacs, respectively. Varian log files also showed no improvement in fluence delivery between the linacs at 3%/3 mm, with median gamma passing rates of 99.97% (99.93%-99.99%) and 99.98% (99.94%-100%) for the Truebeam and 2100CD linacs, respectively. However, log files revealed improved leaf position accuracy and fluence delivery at 1%/1 mm criterion on the Truebeam (99.87%; 99.78%-99.94%) compared with the 2100CD linac (97.87%; 91.93%-99.49%). The overshoot effect, characterized on the 2100CD linac, was not observed on the Truebeam.

Conclusions: The integrated multileaf collimator controller on the Varian Truebeam improves clinical treatment delivery accuracy of step and shoot intensity modulated radiation therapy fields compared with delivery on a Varian C-series linac. © 2014.

Implementation of phantom-less IMRT delivery verification using Varian DynaLog files and R/V output

This study aims to evaluate the use of Varian radiotherapy dynamic treatment log (DynaLog) files to verify IMRT plan delivery as part of a routine quality assurance procedure. Delivery accuracy in terms of machine performance was quantified by multileaf collimator (MLC) position errors and fluence delivery accuracy for patients receiving intensity modulated radiation therapy (IMRT) treatment. The relationship between machine performance and plan complexity, quantified by the modulation complexity score (MCS) was also investigated. Actual MLC positions and delivered fraction of monitor units (MU), recorded every 50 ms during IMRT delivery, were extracted from the DynaLog files. The planned MLC positions and fractional MU were taken from the record and verify system MLC control file. Planned and delivered beam data were compared to determine leaf position errors with and without the overshoot effect. Analysis was also performed on planned and actual fluence maps reconstructed from the MLC control file and delivered treatment log files respectively. This analysis was performed for all treatment fractions for 5 prostate, 5 prostate and pelvic node (PPN) and 5 head and neck (H&N) IMRT plans, totalling 82 IMRT fields in ∼5500 DynaLog files. The root mean square (RMS) leaf position errors without the overshoot effect were 0.09, 0.26, 0.19 mm for the prostate, PPN and H&N plans respectively, which increased to 0.30, 0.39 and 0.30 mm when the overshoot effect was considered. Average errors were not affected by the overshoot effect and were 0.05, 0.13 and 0.17 mm for prostate, PPN and H&N plans respectively. The percentage of pixels passing fluence map gamma analysis at 3%/3 mm was 99.94 ± 0.25%, which reduced to 91.62 ± 11.39% at 1%/1 mm criterion. Leaf position errors, but not gamma passing rate, were directly related to plan complexity as determined by the MCS. Site specific confidence intervals for average leaf position errors were set at -0.03-0.12 mm for prostate and -0.02-0.28 mm for more complex PPN and H&N plans. For all treatment sites confidence intervals for RMS errors with the overshoot was set at 0-0.50 mm and for the percentage of pixels passing a gamma analysis at 1%/1 mm a confidence interval of 68.83% was set also for all treatment sites. This work demonstrates the successful implementation of treatment log files to validate IMRT deliveries and how dynamic log files can diagnose delivery errors not possible with phantom based QC. Machine performance was found to be directly related to plan complexity but this is not the dominant determinant of delivery accuracy.

Sublinear bounds for randomized leader election

This paper concerns randomized leader election in synchronous distributed networks. A distributed leader election algorithm is presented for complete n-node networks that runs in O(1) rounds and (with high probability) uses only O(√ √nlog^3/2n) messages to elect a unique leader (with high probability). When considering the "explicit" variant of leader election where eventually every node knows the identity of the leader, our algorithm yields the asymptotically optimal bounds of O(1) rounds and O(. n) messages. This algorithm is then extended to one solving leader election on any connected non-bipartite n-node graph G in O(τ(. G)) time and O(τ(G)n√log^3/2n) messages, where τ(. G) is the mixing time of a random walk on G. The above result implies highly efficient (sublinear running time and messages) leader election algorithms for networks with small mixing times, such as expanders and hypercubes. In contrast, previous leader election algorithms had at least linear message complexity even in complete graphs. Moreover, super-linear message lower bounds are known for time-efficient deterministic leader election algorithms. Finally, we present an almost matching lower bound for randomized leader election, showing that Ω(n) messages are needed for any leader election algorithm that succeeds with probability at least 1/. e+. ε, for any small constant ε. >. 0. We view our results as a step towards understanding the randomized complexity of leader election in distributed networks.

Human parietal and primary motor cortical interactions are selectively modulated during the transport and grip formation of goal-directed hand actions

Posterior parietal cortex (PPC) constitutes a critical cortical node in the sensorimotor system in which goal-directed actions are computed. This information then must be transferred into commands suitable for hand movements to the primary motor cortex (M1). Complexity arises because reach-to-grasp actions not only require directing the hand towards the object (transport component), but also preshaping the hand according to the features of the object (grip component). Yet, the functional influence that specific PPC regions exert over ipsilateral M1 during the planning of different hand movements remains unclear in humans. Here we manipulated transport and grip components of goal-directed hand movements and exploited paired-pulse transcranial magnetic stimulation (ppTMS) to probe the functional interactions between M1 and two different PPC regions, namely superior parieto-occipital cortex (SPOC) and the anterior region of the intraparietal sulcus (aIPS), in the left hemisphere. We show that when the extension of the arm is required to contact a target object, SPOC selectively facilitates motor evoked potentials, suggesting that SPOC-M1 interactions are functionally specific to arm transport. In contrast, a different pathway, linking the aIPS and ipsilateral M1, shows enhanced functional connections during the sensorimotor planning of grip. These results support recent human neuroimaging findings arguing for specialized human parietal regions for the planning of arm transport and hand grip during goal-directed actions. Importantly, they provide new insight into the causal influences these different parietal regions exert over ipsilateral motor cortex for specific types of planned hand movements

The mediastinal staging accuracy of 18F-Fluorodeoxyglycose Positron Emission Tomography/Computed Tomography in non-small cell lung cancer with variable time intervals to surgery.

BACKGROUND: PET/CT scanning can determine suitability for curative therapy and inform decision making when considering radical therapy in patients with non-small cell lung cancer (NSCLC). Metastases to central mediastinal lymph nodes (N2) may alter such management decisions. We report a 2 year retrospective series assessing N2 lymph node staging accuracy with PET/CT compared to pathological analysis at surgery.

METHODS: Patients with NSCLC attending our centre (excluding those who had induction chemotherapy) who had staging PET/CT scans and pathological nodal sampling between June 2006 and June 2008 were analysed. For each lymph node assessed pathologically, the corresponding PET/CT status was determined. 64 patients with 200 N2 lymph nodes were analysed.

RESULTS: Sensitivity of PET/CT scans for indentifying involved N2 lymph nodes was
39%, specificity 96% and overall accuracy 90%. For individual lymph node analysis, logistic regression demonstrated a significant linear association between PET/CT sensitivity and time from scanning to surgery (p=0.031) but not for specificity and accuracy. Those scanned <9 weeks before pathological sampling were significantly more sensitive (64% >9 weeks, 0% ≥ 9 weeks, p=0.013) and more accurate (94% <9 weeks, 81% ≥ 9 weeks, p=0.007). Differences in specificity were not seen (97% <9 weeks, 91% ≥ 9 weeks, p=0.228). No significant difference in specificity was found at any time point.

CONCLUSIONS: We recommend that if a PET/CT scan is older than 9 weeks, and management would be altered by the presence of N2 nodes, re-staging of the
mediastinum should be undertaken.