Exact bounds for distributed graph colouring

A distributed system is a collection of networked autonomous processing units which must work in a cooperative manner. Currently, large-scale distributed systems, such as various telecommunication and computer networks, are abundant and used in a multitude of tasks. The field of distributed computing studies what can be computed efficiently in such systems. Distributed systems are usually modelled as graphs where nodes represent the processors and edges denote communication links between processors. This thesis concentrates on the computational complexity of the distributed graph colouring problem. The objective of the graph colouring problem is to assign a colour to each node in such a way that no two nodes connected by an edge share the same colour. In particular, it is often desirable to use only a small number of colours. This task is a fundamental symmetry-breaking primitive in various distributed algorithms. A graph that has been coloured in this manner using at most k different colours is said to be k-coloured. This work examines the synchronous message-passing model of distributed computation: every node runs the same algorithm, and the system operates in discrete synchronous communication rounds. During each round, a node can communicate with its neighbours and perform local computation. In this model, the time complexity of a problem is the number of synchronous communication rounds required to solve the problem. It is known that 3-colouring any k-coloured directed cycle requires at least ½(log* k - 3) communication rounds and is possible in ½(log* k + 7) communication rounds for all k ≥ 3. This work shows that for any k ≥ 3, colouring a k-coloured directed cycle with at most three colours is possible in ½(log* k + 3) rounds. In contrast, it is also shown that for some values of k, colouring a directed cycle with at most three colours requires at least ½(log* k + 1) communication rounds. Furthermore, in the case of directed rooted trees, reducing a k-colouring into a 3-colouring requires at least log* k + 1 rounds for some k and possible in log* k + 3 rounds for all k ≥ 3. The new positive and negative results are derived using computational methods, as the existence of distributed colouring algorithms corresponds to the colourability of so-called neighbourhood graphs. The colourability of these graphs is analysed using Boolean satisfiability (SAT) solvers. Finally, this thesis shows that similar methods are applicable in capturing the existence of distributed algorithms for other graph problems, such as the maximal matching problem.

Kognitiva system i namngivningen av finländska handelsfartyg 1838-1938

This dissertation is an onomastic study of Finland s stock of ship names (nautonomasticon) recorded over the period 1838 1938. The primary material investigated consists of 2 066 examples of ship names from the fleets of coastal towns, distributed over five sample years. The material is supplemented with two bodies of comparative data; one that consists of 2 535 examples of boat names from the archipelago area at the corresponding time, and another that comprises 482 examples of eighteenth century Finnish ship names. This study clarifies the categories of names that appear the frequency of the names, formation, morphology, linguistic origin, functions, and semantic qualities. By comparing the material with boat names from previous centuries, and from other countries, the characteristics of Finnish vessel names are further highlighted. Additional clarification is brought to the chronological, regional, and social variations, and to the emergence of various forms of systematic naming. This dissertation builds on older research from other countries, and uses traditional onomastic methods alongside a more modern methodology. The approach is interdisciplinary, meaning that the names are explored using facts not only from nautical history, but also from a range of other historical disciplines such as economics, culture, art, and literature. In addition, the approach is socio-onomastic, i.e. that the variations in names are studied in a societal context. Using a synchronised perspective, cognitive linguistic theories have provided the tools for this exploration into the metaphorical and the prototypical meaning of the names, and the semantic domains that the names create. The quantitative analysis has revealed the overall picture of Finnish boat names. Personal names, names from mythology, and place names, emerge as significant categories, alongside nonproprial names in Swedish and Finnish. The interdisciplinary perspective has made it possible to explain certain trends in the stock of boat names, for example, the predisposition towards names from classical mythology, the breakthrough of names taken from the national epos Kalevala, names in the Finnish language from around the middle of the nineteenth century, and the continuing rise of place names during the latter part of the period 1838 1938. The socio-onomastic perspective has also identified clear differences between those ship names used in towns, and those ship names used in the archipelago, and it has clarified how naming conventions tend to spread from town centres to peripheral areas. The cognitive linguistic methods have revealed that the greater part of the vessel names can be interpreted as metaphors, in particular personifications, and that many names are related in their content and also form semantic networks and cognitive systems. The results indicate that there is a mental nautonomasticon that consists of a standard set of traditional ship names, but they also reveal the existence of conscious or unconscious cognitive systems (rules and conventions) that guide the naming of boats.

Processing of Stimulus Repetition and Change in the Somatosensory System: Recordings of Electrical and Magnetic Brain Responses

In the present work, effects of stimulus repetition and change in a continuous stimulus stream on the processing of somatosensory information in the human brain were studied. Human scalp-recorded somatosensory event-related potentials (ERPs) and magnetoencephalographic (MEG) responses rapidly diminished with stimulus repetition when mechanical or electric stimuli were applied to fingers. On the contrary, when the ERPs and multi-unit a ctivity (MUA) were directly recorded from the primary (SI) and secondary (SII) somatosensory cortices in a monkey, there was no marked decrement in the somatosensory responses as a function of stimulus repetition. These results suggest that this rate effect is not due to the response diminution in the SI and SII cortices. Obviously the responses to the first stimulus after a long "silent" period are nhanced due to unspecific initial orientation, originating in more broadly distributed and/or deeper neural structures, perhaps in the prefrontal cortices. With fast repetition rates not only the late unspecific but also some early specific somatosensory ERPs were diminished in amplitude. The fast decrease of the ERPs as a function of stimulus repetition is mainly due to the disappearance of the orientation effect and with faster repetition rates additively due to stimulus specific refractoriness. A sudden infrequent change in the continuous stimulus stream also enhanced somatosensory MEG responses to electric stimuli applied to different fingers. These responses were quite similar to those elicited by the deviant stimuli alone when the frequent standard stimuli were omitted. This enhancement was obviously due to the release from refractoriness because the neural structures generating the responses to the infrequent deviants had more time to recover from the refractoriness than the respective structures for the standards. Infrequent deviant mechanical stimuli among frequent standard stimuli also enhanced somatosensory ERPs and, in addition, they elicited a new negative wave which did not occur in the deviants-alone condition. This extra negativity could be recorded to deviations in the stimulation site and in the frequency of the vibratory stimuli. This response is probably a somatosensory analogue of the auditory mismatch negativity (MMN) which has been suggested to reflect a neural mismatch process between the sensory input and the sensory memory trace.