A Touch of Red : Archaeological and Ethnographic Approaches to Interpreting Finnish Rock Paintings

Approximately 125 prehistoric rock paintings have been found in the modern territory of Finland. The paintings were done with red ochre and are almost without exception located on steep lakeshore cliffs associated with ancient water routes. Most of the sites are found in the central and eastern parts of the country, especially on the shores of Lakes Päijänne and Saimaa. Using shore displacement chronology, the art has been dated to ca. 5000 – 1500 BC. It was thus created mainly during the Stone Age and can be associated with the so-called ‘Comb Ware’ cultures of the Subneolithic period. The range of motifs is rather limited, consisting mainly of schematic depictions of stick-figure humans, elks, boats, handprints and geometric signs. Few paintings include any evidence of narrative scenes, making their interpretation a rather difficult task. In Finnish archaeological literature, the paintings have traditionally been associated with ’sympathetic’ hunting magic, or the belief that the ritual shooting of the painted animals would increase hunting luck. Some writers have also suggested totemistic and shamanistic readings of the art. This dissertation is a critical review of the interpretations offered of Finnish rock art and an exploration of the potentials of archaeological and ethnographic research in increasing our knowledge of its meaning. Methods used include ’formal’ approaches such as archaeological excavation, landscape analysis and the application of neuropsychological research to the study of rock art, as well as ethnographically ’informed’ approaches that make use of Saami and Baltic Finnish ethnohistorical sources in interpretation. In conclusion, it is argued that although North European hunter-gatherer rock art is often thought to lie beyond the reach of ‘informed’ knowledge, the exceptional continuity of prehistoric settlement in Finland validates the informed approach in the interpretation of Finnish rock paintings. The art can be confidently associated with shamanism of the kind still practiced by the Saami of Northern Fennoscandia in the historical period. Evidence of similar shamanistic practices, concepts and cosmology are also found in traditional Finnish-Karelian epic poetry. Previous readings of the art based on ‘hunting magic’ and totemism are rejected. Most of the paintings appear to depict experiences of falling into a trance, of shamanic metamorphosis and trance journeys, and of ‘spirit helper’ beings comparable to those employed by the Saami shaman (noaidi). As demonstrated by the results of an excavation at the rock painting of Valkeisaari, the painted cliffs themselves find a close parallel in the Saami cult of the 'sieidi', or sacred cliffs and boulders worshipped as expressing a supernatural power. Like the Saami, the prehistoric inhabitants of the Finnish Lake Region seem to have believed that certain cliffs were ’alive’ and inhabited by the spirit helpers of the shaman. The rock paintings can thus be associated with shamanic vision quests, and the making of ‘art’ with an effort to socialize the other members of the community, especially the ritual specialists, with trance visions. However, the paintings were not merely to be looked at. The red ochre handprints pressed on images of elks, as well as the fact that many paintings appear ’smeared’, indicate that they were also to be touched – perhaps in order to tap into the supernatural potency inherent in the cliff and in the paintings of spirit animals.

Optimisation Problems in Wireless Sensor Networks : Local Algorithms and Local Graphs

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

Analysing local algorithms in location-aware quasi-unit-disk graphs

A local algorithm with local horizon r is a distributed algorithm that runs in r synchronous communication rounds; here r is a constant that does not depend on the size of the network. As a consequence, the output of a node in a local algorithm only depends on the input within r hops from the node. We give tight bounds on the local horizon for a class of local algorithms for combinatorial problems on unit-disk graphs (UDGs). Most of our bounds are due to a refined analysis of existing approaches, while others are obtained by suggesting new algorithms. The algorithms we consider are based on network decompositions guided by a rectangular tiling of the plane. The algorithms are applied to matching, independent set, graph colouring, vertex cover, and dominating set. We also study local algorithms on quasi-UDGs, which are a popular generalisation of UDGs, aimed at more realistic modelling of communication between the network nodes. Analysing the local algorithms on quasi-UDGs allows one to assume that the nodes know their coordinates only approximately, up to an additive error. Despite the localisation error, the quality of the solution to problems on quasi-UDGs remains the same as for the case of UDGs with perfect location awareness. We analyse the increase in the local horizon that comes along with moving from UDGs to quasi-UDGs.

Compression of Weighted Graphs

We propose to compress weighted graphs (networks), motivated by the observation that large networks of social, biological, or other relations can be complex to handle and visualize. In the process also known as graph simplication, nodes and (unweighted) edges are grouped to supernodes and superedges, respectively, to obtain a smaller graph. We propose models and algorithms for weighted graphs. The interpretation (i.e. decompression) of a compressed, weighted graph is that a pair of original nodes is connected by an edge if their supernodes are connected by one, and that the weight of an edge is approximated to be the weight of the superedge. The compression problem now consists of choosing supernodes, superedges, and superedge weights so that the approximation error is minimized while the amount of compression is maximized. In this paper, we formulate this task as the 'simple weighted graph compression problem'. We then propose a much wider class of tasks under the name of 'generalized weighted graph compression problem'. The generalized task extends the optimization to preserve longer-range connectivities between nodes, not just individual edge weights. We study the properties of these problems and propose a range of algorithms to solve them, with dierent balances between complexity and quality of the result. We evaluate the problems and algorithms experimentally on real networks. The results indicate that weighted graphs can be compressed efficiently with relatively little compression error.