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

<p>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 <em>v</em> and <em>w</em> whose distance would have been <em>l</em> in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most <em>l</em> log <em>n</em> in the actual graph, where <em>n</em> is the total number of vertices seen so far. Similarly, at any point, a node <em>v</em> whose degree would have been <em>d</em> in the graph with adversarial insertions only, will have degree at most 3<em>d</em> 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.</p>

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.

Transient Polymorphism in NaCl

<p>We introduce a new, collective variable (CV) that can be used to increase the frequency with which nucleation events are observed in biased atomistic simulations. This CV forces the ions to aggregate into clusters but does not force the ions to order themselves in a particular pattern. We perform metadynamics simulations using this CV in order to examine nucleation in a solution of sodium chloride and find that for small cluster sizes the usual bulk rocksalt structure is less stable than a structure that resembles wurtzite.</p>

A drive-by inspection system via vehicle moving force identification

This paper presents a novel method to carry out monitoring of transport infrastructure such as pavements and bridges through the analysis of vehicle accelerations. An algorithm is developed for the identification of dynamic vehicle-bridge interaction forces using the vehicle response. Moving force identification theory is applied to a vehicle model in order to identify these dynamic forces between the vehicle and the road and/or bridge. A coupled half-car vehicle-bridge interaction model is used in theoretical simulations to test the effectiveness of the approach in identifying the forces. The potential of the method to identify the global bending stiffness of the bridge and to predict the pavement roughness is presented. The method is tested for a range of bridge spans using theoretical simulations and the influences of road roughness and signal noise on the accuracy of the results are investigated.

Enabling Complexity-Performance Trade-Offs for Successive Cancellation Decoding of Polar Codes

Polar codes are one of the most recent advancements in coding theory and they have attracted significant interest. While they are provably capacity achieving over various channels, they have seen limited practical applications. Unfortunately, the successive nature of successive cancellation based decoders hinders fine-grained adaptation of the decoding complexity to design constraints and operating conditions. In this paper, we propose a systematic method for enabling complexity-performance trade-offs by constructing polar codes based on an optimization problem which minimizes the complexity under a suitably defined mutual information based performance constraint. Moreover, a low-complexity greedy algorithm is proposed in order to solve the optimization problem efficiently for very large code lengths.

Towards a general framework for information fusion

Depending on the representation setting, different combination rules have been proposed for fusing information from distinct sources. Moreover in each setting, different sets of axioms that combination rules should satisfy have been advocated, thus justifying the existence of alternative rules (usually motivated by situations where the behavior of other rules was found unsatisfactory). These sets of axioms are usually purely considered in their own settings, without in-depth analysis of common properties essential for all the settings. This paper introduces core properties that, once properly instantiated, are meaningful in different representation settings ranging from logic to imprecise probabilities. The following representation settings are especially considered: classical set representation, possibility theory, and evidence theory, the latter encompassing the two other ones as special cases. This unified discussion of combination rules across different settings is expected to provide a fresh look on some old but basic issues in information fusion.

Analysing Web-Orchestrations Under Stress Using Uncertainty Profiles

An orchestration is a multi-threaded computation that invokes a number of remote services. In practice, the responsiveness of a web-service fluctuates with demand; during surges in activity service responsiveness may be degraded, perhaps even to the point of failure. An uncertainty profile formalizes a user's perception of the effects of stress on an orchestration of web-services; it describes a strategic situation, modelled by a zero-sum angel���daemon game. Stressed web-service scenarios are analysed, using game theory, in a realistic way, lying between over-optimism (services are entirely reliable) and over-pessimism (all services are broken). The ���resilience��� of an uncertainty profile can be assessed using the valuation of its associated zero-sum game. In order to demonstrate the validity of the approach, we consider two measures of resilience and a number of different stress models. It is shown how (i) uncertainty profiles can be ordered by risk (as measured by game valuations) and (ii) the structural properties of risk partial orders can be analysed.

DEX: self-healing expanders

<p class="Para" style="box-sizing: border-box; margin-top: 1em; margin-bottom: 1.2em; word-break: break-word;">We present a fully-distributed self-healing algorithm��dex��that maintains a constant degree expander network in a dynamic setting. To the best of our knowledge, our algorithm provides the first efficient distributed construction of expanders���whose expansion properties hold<em class="EmphasisTypeItalic" style="box-sizing: border-box;">deterministically</em>���that works even under an all-powerful adaptive adversary that controls the dynamic changes to the network (the adversary has unlimited computational power and knowledge of the entire network state, can decide which nodes join and leave and at what time, and knows the past random choices made by the algorithm). Previous distributed expander constructions typically provide only��<em class="EmphasisTypeItalic" style="box-sizing: border-box;">probabilistic</em>��guarantees on the network expansion which<em class="EmphasisTypeItalic" style="box-sizing: border-box;">rapidly degrade</em>��in a dynamic setting; in particular, the expansion properties can degrade even more rapidly under��<em class="EmphasisTypeItalic" style="box-sizing: border-box;">adversarial</em>��insertions and deletions. Our algorithm provides efficient maintenance and incurs a low overhead per insertion/deletion by an adaptive adversary: only��O(logn)O(log���n)��rounds and��O(logn)O(log���n)��messages are needed with high probability (<em class="EmphasisTypeItalic" style="box-sizing: border-box;">n</em>��is the number of nodes currently in the network). The algorithm requires only a constant number of topology changes. Moreover, our algorithm allows for an efficient implementation and maintenance of a distributed hash table on top of��dex�� with only a constant additional overhead. Our results are a step towards implementing efficient self-healing networks that have��<em class="EmphasisTypeItalic" style="box-sizing: border-box;">guaranteed</em>��properties (constant bounded degree and expansion) despite dynamic changes.</p><p class="SimplePara" style="box-sizing: border-box;">Gopal Pandurangan has been supported in part by Nanyang Technological University Grant M58110000, Singapore Ministry of Education (MOE) Academic Research Fund (AcRF) Tier 2 Grant MOE2010-T2-2-082, MOE AcRF Tier 1 Grant MOE2012-T1-001-094, and the United States-Israel Binational Science Foundation (BSF) Grant 2008348. Peter Robinson has been supported by Grant MOE2011-T2-2-042 ���Fault-tolerant Communication Complexity in Wireless Networks��� from the Singapore MoE AcRF-2. Work done in part while the author was at the Nanyang Technological University and at the National University of Singapore. Amitabh Trehan has been supported by the Israeli Centers of Research Excellence (I-CORE) program (Center No. 4/11). Work done in part while the author was at Hebrew University of Jerusalem and at the Technion and supported by a Technion fellowship.</p>

The Use of Audio Podcasts to Enhance the Delivery of a Computer Networks Course

Experience obtained in the support of mobile learning using podcast audio is reported. The paper outlines design, storage and distribution via a web site. An initial evaluation of the uptake of the approach in a final year computing module was undertaken. Audio objects were tailored to meet different pedagogical needs resulting in a repository of persistent glossary terms and disposable audio lectures distributed by podcasting. An aim of our approach is to document the interest from the students, and evaluate the potential of mobile learning for supplementing revision