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.

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.

How fragmented was the British Holocene wildwood? Perspectives on the “Vera” grazing debate from the fossil beetle record

The reconstruction and structure of the European Holocene “wildwood” has been the focus of considerable academic debate. The ability of palaeoecological data and particularly pollen analysis to accurately reflect the density of wildwood canopy has also been widely discussed. Fossil insects, as a proxy for vegetation and landscape structure, provide a potential approach to address this argument. Here, we present a review and re-analysis of 36 early and mid-Holocene (9500-2000 cal BC) sub-fossil beetle assemblages from Britain, examining percentage values of tree, open ground and dung beetles as well as tree host data to gain an insight into vegetation structure, the role of grazing animals in driving such structure and establish independently the importance of different types of trees and associated shading in the early Holocene “wildwood”. Open indicator beetle species are persistently present over the entire review period, although they fluctuate in importance. During the early Holocene (9500-6000 cal BC), these indicators are initially high, at levels which are not dissimilar to modern data from pasture woodland. However, during the latter stages of this and the next period, 6000-4000 cal BC, open ground and pasture indicators decline and are generally low compared with previously. Alongside this pattern, we see woodland indicators generally increase in importance, although there are significant local fluctuations. Levels of dung beetles are mostly low over these periods, with some exceptions to this pattern, especially towards the end of the Mesolithic and in floodplain areas. Host data associated with the fossil beetles indicate that trees associated with lighter canopy conditions such as oak, pine, hazel and birch are indeed important components of the tree canopy during the earlier Holocene (c. 9500-6000 cal BC), in accordance with much of the current pollen literature. Beetles associated with more shade-tolerant trees (such as lime and elm) become more frequent in the middle Holocene (6000-4000 cal BC) suggesting that at this stage the woodland canopy was less open than previously, although open ground and pasture areas appear to have persisted in some locations. The onset of agriculture (4000-2000 cal BC) coincides with significant fluctuations in woodland composition and taxa. This is presumably as a result of human impact, although here there are significant regional variations. There are also increases in the amounts of open ground represented and especially in the levels of dung beetles present in faunas, suggesting there is a direct relationship between the activities of grazing animals and the development of more open areas. One of the most striking aspects of this review is the variable nature of the landscape suggested by the palaeoecological data, particularly but not exclusively with the onset of agriculture: some earlier sites indicate high variability between levels of tree-associated species on the one hand and the open ground beetle fauna on the other, indicating that in some locations, open areas were of local significance and can be regarded as important features of the Holocene landscape. The role of grazing animals in creating these areas of openness was apparently minimal until the onset of the Neolithic.

Joined Spectral Trees for Scalable SPIHT-Based Multispectral Image Compression

In this paper, the compression of multispectral images is addressed. Such 3-D data are characterized by a high correlation across the spectral components. The efficiency of the state-of-the-art wavelet-based coder 3-D SPIHT is considered. Although the 3-D SPIHT algorithm provides the obvious way to process a multispectral image as a volumetric block and, consequently, maintain the attractive properties exhibited in 2-D (excellent performance, low complexity, and embeddedness of the bit-stream), its 3-D trees structure is shown to be not adequately suited for 3-D wavelet transformed (DWT) multispectral images. The fact that each parent has eight children in the 3-D structure considerably increases the list of insignificant sets (LIS) and the list of insignificant pixels (LIP) since the partitioning of any set produces eight subsets which will be processed similarly during the sorting pass. Thus, a significant portion from the overall bit-budget is wastedly spent to sort insignificant information. Through an investigation based on results analysis, we demonstrate that a straightforward 2-D SPIHT technique, when suitably adjusted to maintain the rate scalability and carried out in the 3-D DWT domain, overcomes this weakness. In addition, a new SPIHT-based scalable multispectral image compression algorithm is used in the initial iterations to exploit the redundancies within each group of two consecutive spectral bands. Numerical experiments on a number of multispectral images have shown that the proposed scheme provides significant improvements over related works.

A general framework for measuring inconsistency through minimal inconsistent sets

Hunter and Konieczny explored the relationships between measures of inconsistency for a belief base and the minimal inconsistent subsets of that belief base in several of their papers. In particular, an inconsistency value termed MIVC, defined from minimal inconsistent subsets, can be considered as a Shapley Inconsistency Value. Moreover, it can be axiomatized completely in terms of five simple axioms. MinInc, one of the five axioms, states that each minimal inconsistent set has the same amount of conflict. However, it conflicts with the intuition illustrated by the lottery paradox, which states that as the size of a minimal inconsistent belief base increases, the degree of inconsistency of that belief base becomes smaller. To address this, we present two kinds of revised inconsistency measures for a belief base from its minimal inconsistent subsets. Each of these measures considers the size of each minimal inconsistent subset as well as the number of minimal inconsistent subsets of a belief base. More specifically, we first present a vectorial measure to capture the inconsistency for a belief base, which is more discriminative than MIVC. Then we present a family of weighted inconsistency measures based on the vectorial inconsistency measure, which allow us to capture the inconsistency for a belief base in terms of a single numerical value as usual. We also show that each of the two kinds of revised inconsistency measures can be considered as a particular Shapley Inconsistency Value, and can be axiomatically characterized by the corresponding revised axioms presented in this paper.