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 l in the graph formed by considering only the adversarial insertions (not the adversarial deletions), will be at distance at most l 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 degree would 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.

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.

Chironomid-based reconstructions of summer air temperature from lake deposits in Lyndon Stream, New Zealand spanning the MIS 3/2 transition

We present chironomid-based temperature reconstructions from lake sediments deposited between ca 26,600 cal yr BP and 24,500 cal yr BP from Lyndon Stream, South Island, New Zealand. Summer (February mean) temperatures averaged 1 1C cooler, with a maximum inferred cooling of 3.7 1C. These estimates corroborate macrofossil and beetle-based temperature inferences from the same site and suggest climate amelioration (an interstadial) at this time. Other records from the New Zealand region also show a large degree of variability during the late Otiran glacial sequence (34,000–18,000 cal yr BP) including a phase of warming at the MIS 2/3 transition and a maximum cooling that did not occur until the global LGM (ca 20,000 cal yr BP). The very moderate cooling identified here at the MIS 2/3 transition confirms and enhances the long-standing discrepancy in New Zealand records between pollen and other proxies. Low abundances (o20%) of canopy tree pollen in records from late MIS 3 to the end of MIS 2 cannot be explained by the minor (o5 1C) cooling inferred from this and other studies unless other environmental parameters are considered. Further work is required to address this critical issue.

High-precision radiocarbon measurements of contemporaneous tree-ring wood from the British Isles and New Zealand: AD 1850-950.

The University of Waikato, Hamilton, New Zealand and The Queen's University of Belfast, Northern Ireland radiocarbon dating laboratories have undertaken a series of high-precision measurements on decadal samples of dendrochronologically dated oak (Quercus petraea) from Great Britain and cedar (Libocedrus bidwillii) and silver pine (Lagarostrobos colensoi) from New Zealand. The results show an average hemispheric offset over the 900 yr of measurement of 40±13 yr. This value is not constant but varies with a periodicity of about 130 yr. The Northern Hemisphere measurements confirm the validity of the Pearson et al. (1986) calibration dataset.

Micromorphology of lamellae formed in an alluvial soil, Big Pine Tree Archeological Site, South Carolina

The formation of lamellae in soils is not clearly understood. The objectives of this study are to examine the microscopical characteristics of selected well developed lamellae inorder to identify the major processes involved in their formation at the Big Pine Tree Archaeological site on the Savannah River, South Carolina. Well developed lamellae have formed in a fine sandy alluvial soil that is about 11,000 to 12,000 years old. In the field, these lamellae are observed as 1 to 4.2 cm thick horizontal layers having a smooth upper and a wavy, sometimes irregular, lower boundary with adjacent interlamellae horizons. Soil thin sections reveal denser accumulations of brown fine silt and clay coatings in the upper and lower sections of the lamellae. The center of the lamellae has mainly orange highly oriented discontinuous clay coatings bridging quartz grains and some silt accumulations. Although, horizontal layering of denser areas (accumulations of fine silt and clay coatings) is also observed in the middle of the lamellae. The interlamellae horizons are mainly loose quartz grains. Low total carbon values (

Novel frenatins from the skin of the Australasian Giant White-lipped tree frog, Litoria infrafrenata: cloning of precursor cDNAs and identification in defensive skin secretion.

The Australasian anuran amphibian genus Litoria, contains many phenotypically-diverse species as a result of radial evolution of an ancestral species into different biotopes much in the manner of the indigenous marsupial mammals. In common with members of the Central/South American genus Phyllomedusa, their specialized skin granular glands are factories for the production of a plethora of biologically-active peptides. Here we report a more detailed study of those present in the defensive skin secretion of the Australasian giant white-lipped tree frog, Litoria infrafrenata, and, for the first time, we have identified three novel frenatins by deduction of primary structures from cDNAs that were cloned from a library constructed from lyophilized skin secretion using a recently-developed technique. All open-reading frames consisted of a putative signal peptide and an acidic pro-region followed by a single copy of a frenatin peptide. Processed peptides corresponding in molecular mass to the deduced molecular masses of frenatins (named 1.1, 3, 3.1 and 4.1) were identified in the same secretion sample using HPLC and mass spectroscopy. The application of this technique thus permits parallel peptidomic and transcriptomic analyzes on the same lyophilized skin secretion sample circumventing sacrifice of specimens from endangered herpetofauna.

In vitro activity of tea-tree oil against clinical skin isolates of meticillin-resistant and -sensitive Staphylococcus aureus and coagulase-negative staphylococci growing planktonically and as biofilms

The susceptibility of Staphylococcus aureus [meticillin-resistant (MRSA) and meticillin-sensitive (MSSA)] and coagulase-negative staphylococci (CoNS), which respectively form part of the transient and commensal skin flora, to tea-tree oil (TTO) was compared using broth microdilution and quantitative in vitro time-kill test methods. MRSA and MSSA isolates were significantly less susceptible than CoNS isolates, as measured by both MIC and minimum bactericidal concentration. A significant decrease in the mean viable count of all isolates in comparison with the control was seen at each time interval in time-kill assays. However, the only significant difference in the overall mean log(10) reduction in viable count between the groups of isolates was between CoNS and MSSA at 3 h, with CoNS isolates demonstrating a significantly lower mean reduction. To provide a better simulation of in vivo conditions on the skin, where bacteria are reported to grow as microcolonies encased in glycocalyx, the bactericidal activity of TTO against isolates grown as biofilms was also compared. Biofilms formed by MSSA and MRSA isolates were completely eradicated following exposure to 5 % TTO for 1 h. In contrast, of the biofilms formed by the nine CoNS isolates tested, only five were completely killed, although a reduction in viable count was apparent for the other four isolates. These results suggest that TTO exerts a greater bactericidal activity against biofilm-grown MRSA and MSSA isolates than against some biofilm-grown CoNS isolates.