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.

Elämänmuutoksen, jännityksen ja asiantuntijuuden representointi Veikkaus Oy:n mainonnassa vuosina 1970— 2006

Aim of this master's thesis paper for consumer economics, is to research gambling advertisements in Finland over a period of 35 years, from 1970 to 2006. Veikkaus Oy (later Veikkaus), was founded in 1940, as one of the three licensed gambling organizations in Finland. Material for the current research comprised 1494 advertisements published by Veikkaus in newspapers and magazines at that time. Veikkaus has the exclusive licence to organize lotto games, sport games, instant games and other draw games in Finland. The other two operators, The Finnish Slot Machine Association RAY and Fintoto (on-track horse betting), were not included in the current analysis. This study has been completed according to research contract and grand by the Finnish Foundation for Gaming Research (Pelitoiminnan tutkimussäätiö). In general, advertisements reflect surrounding culture and time, and their message is built on stratified meanings, symbols and codes. Advertising draws the viewer's attention, introduces the advertised subject, and finally, affects the individual's consumption habits. However, advertisements not only work on individual level, but also influence public perception of the advertised product. Firstly, in order to assess gambling as a phenomenon, this paper discusses gambling as consumer behaviour, and also reviews history of gambling in Finland. Winning is a major feature of gambling, and dreaming about positive change of life is a centre of most gambling ads. However, perceived excitement through risk of losing can also be featured in gambling ads. Secondly, this study utilizes Veikkaus’ large advertising archives, were advertising data is analyzed by content analysis and the semiotic analysis. Two methods have been employed to support analyzing outcome in a synergistic way. Content analysis helps to achieve accuracy and comprehensiveness. Semiotic analysis allows deeper and more sensitive analysis to emerged findings and occurrences. It is important to understand the advertised product, as advertising is bound to the culture and time. Hence, to analyze advertising, it is important to understand the environment where the ads appear. Content analysis of Veikkaus data discovered the main gambling and principal advertisement style for each.period. Interestingly, nearly half of Veikkaus’ advertisements promoted topic other than “just winning the bet”. Games of change, like Lotto, typically advertised indirectly represented dreams about winning. In the category of skill gambling, features were represented as investment, and the excitement of sporting expertise was emphasized. In addition, there were a number of gambling ads that emphasize social responsibility of Veikkaus as a government guided organization. Semiotic methods were employed to further elaborate on findings of content analysis. Dreaming in the advertisements was represented by the product of symbols, (e.g. cars and homes) that were found to have significance connection with each other. Thus, advertising represents change of life obtained by the winning. Interestingly, gambling ads promoting jackpots were often representing religious symbolisms. Ads promoting social responsibility were found to be the most common during economical depression of the 90’s. Deeper analysis showed that at that time, advertisements frequently represented depression-related meanings, such as unemployment and bank loans. Skill gaming ads were often represented by sports expertise – late 90’s, their number started sky rocketing, and continued increasing until 2006 (when this study ended). One may conclude that sport betting draws its meanings from the relevant consumer culture, and from the rules and features of the betted sport.

Numeroiden harhaa vai toteutuksen työkaluja? -indikaattorien käyttö maatalouden ympäristöpoliittisessa suunnittelussa

This research focused on indicators with the aim of recognizing the main characters of this particular tool. The planning and use of Finnish sustainability indicators for natural resource management was examined as well as the experiences about the international sets of agri-environmental indicators were described. In both cases, the actual utilization of information was found to be quite minimal. Indicators have succeeded in bringing more of environmental information into the processes of decision making, but information has not been directly shifted into the actions of natural resource management. The concept of technical use of indicators was presented and considered as a possible explanation for the failures of information transfer and communication. Traditionally indicators have been used in order to recognize and describe the performance of certain system; to provide clear operative message for the actors. In policy planning, the situation is essentially different. We may lack both the jointly shared and accepted objectives of development as well the reliable and representative methods for measuring the issue under attention. Therefore, the technical orientation of using indicators may cause several problems at the policy forum. The study identified the risks of 1) reduced informative basis of decision-making, 2) narrowed approach of interpreting the data, 3) the focus on the issues that already are best documented and provides the most representative data series, and 4) the risks of losing the systemic viewpoints while focusing on measurable details of the system. Technical use of indicators may also result the excessive focus on information while being detached from the actions. With sustainability indicators, the major emphasis was indeed paid with producing information while the reality of agricultural practices was left mostly unaffected. Therefore, the essential process of social learning, where actions and producing of relevant information are alternating was neither realized. This study underlines the complexity of information transfer, mutual communication and the learning of new practices. Besides the information and measurable number people also need personal experiences and interesting stories, which make them to understand the meaning of information in their own lives. Particularly important this is for thechildren, who are studying for to be the future decision-makers of food system; in production as well as the in consumption of food. Numbers will be useful tools of management as soon there exists the awareness of the direction, where to strive for.

Nucleotide sequence of the 3terminal region of belladonna mottle virus (renamed Physalis mottle virus) RNA and analysis of the evolutionary relationships among tymoviral coat proteins

The 3' terminal 1255 nt sequence of Physalis mottle virus (PhMV) genomic RNA has been determined from a set of overlapping cDNA clones. The open reading frame (ORF) at the 3' terminus corresponds to the amino acid sequence of the coat protein (CP) determined earlier except for the absence of the dipeptide, Lys-Leu, at position 110-111. In addiition, the sequence upstream of the CP gene contains the message coding for 178 amino acid residues of the C-terminus of the putative replicase protein (RP). The sequence downstream of the CP gene contains an untranslated region whose terminal 80 nucleotides can be folded into a characteristic tRNA-like structure. A phylogenetic tree constructed after aligning separately the sequence of the CP, the replicase protein (RP) and the tRNA-like structure determined in this study with the corresponding sequences of other tymoviruses shows that PhMV wrongly named belladonna mottle virus [BDMV(I)] is a separate tymovirus and not another strain of BDMV(E) as originally envisaged. The phylogenetic tree in all the three cases is identical showing that any subset of genomic sequence of sufficient length can be used for establishing evolutionary relationships among tymoviruses.

Design of clutter-rejecting compact pulse bursts with amplitude modulation and frequency-shift keying

A method is presented for the design of compact pulse burst signals, with amplitude and frequency stepping between individual pulses, for optimum rejection of radar clutter distributed arbitrarily in range. The method is illustrated by an example. It is shown that amplitude stepping plays a useful role only when the reciprocal of the individual pulse width is not insignificant compared to the bandwidth permitted to the signal. As an important and useful subclass of the amplitude-and-frequency-stepped signals, constant amplitude FSK bursts are studied and the extent of loss of clutter performance due to amplitude flattening is evaluated.

Cox-2, tenascin, CRP, and ingraft chimerism in a model of post-transplant obliterative bronchiolitis

Chronic rejection in the form of obliterative bronchiolitis (OB) is the major cause of death 5 years after lung transplantation. The exact mechanism of OB remains unclear. This study focused on the role of cyclo-oxygenase (COX) -2, tenascin, and C-reactive protein (CRP) expression, and the occurrence of ingraft chimerism (= cells from two genetically distinct individuals in a same individual) in post-transplant OB development. In our porcine model, OB developed invariably in allografts, while autografts stayed patent. The histological changes were similar to those seen in human OB. In order to delay or prevent obliteration, animals were medicated according to certain protocol. In the beginning of the bronchial allograft reaction, COX-2 induction occurred in airway epithelial cells prior to luminal obliteration. COX-2 expression in macrophages and fibroblasts paralleled the onset of inflammation and fibroblast proliferation. This study demonstrated for the first time, that COX-2 expression is associated with the early stage of post- transplant obliterative airway disease. Tenascin expression in the respiratory epithelium appeared to be predictive of histologic features observed in human OB, and influx of immune cells. Expression in the bronchial wall and in the early obliterative lesions coincided with the onset of onset of fibroblast and inflammatory cell proliferation in the early stage of OB and was predictive of further influx of inflammatory and immune cells. CRP expression in the bronchial wall coincided with the remodelling process. High grade of bronchial wall CRP staining intensity predicted inflammation, accelerated fibroproliferation, and luminal obliteration, which are all features of OB. In the early obliterative plaque, majority of cells expressed CRP, but in mature, collagen-rich plaque, expression declined. Local CRP expression might be a response to inflammation and it might promote the development of OB. Early appearance of chimeric (= recipient-derived) cells in the graft airway epithelium predicted epithelial cell injury and obliteration of the bronchial lumen, which both are features of OB. Chimeric cells appeared in the airway epithelium after repair following transplantation-induced ischemic injury. Ingraft chimerism might be a mechanism to repair alloimmune-mediated tissue injury and to protect allografts from rejection after transplantation. The results of this study indicate, that COX-2, tenascin, CRP, and ingraft chimerism have a role in OB development. These findings increase the understanding of the mechanisms of OB, which may be beneficial in further development of diagnostic options.

The Home of Hearing : George Lindbeck's understanding of community

The aim of this thesis was to examine the understanding of community in George Lindbeck s The Nature of Doctrine. Intrinsic to this question was also examining how Lindbeck understands the relation between the text and the world which both meet in a Christian community. Thirdly this study also aimed at understanding what the persuasiveness of this understanding depends on. The method applied for this task was systematic analysis. The study was conducted by first providing an orientation into the nontheological substance of the ND which was assumed useful with respect to the aim of this study. The study then went on to explore Lindbeck in his own context of postliberal theology in order to see how the ND was received. It also attempted to provide a picture of how the ND relates to Lindbeck as a theologian. The third chapter was a descriptive analysis into the cultural-linguistic perspective, which is understood as being directly proportional to his understanding of community. The fourth chapter was an analysis into how the cultural-linguistic perspective sees the relation between the text and the world. When religion is understood from a cultural-linguistic perspective, it presents itself as a cultural-linguistic entity, which Lindbeck understands as a comprehensive interpretive scheme which structures human experience and understanding of oneself and the world in which one lives. When one exists in this entity, it is the entity which shapes the subjectivities of all those who are at home in this entity which makes participation in the life of a cultural linguistic entity a condition for understanding it. Religion is above all an external word that moulds and shapes our religious existence and experience. Understanding faith then as coming from hearing, is something that correlates with the cultural-linguistic depiction of reality. Religion informs us of a religious reality, it does not originate in any way from ourselves. This externality linked to the axiomatic nature of religion is also something that distinguishes Lindbeck sharply from liberalist tendencies, which understand religion as ultimately expressing the prereflective depths of the inner self. Language is the central analogy to understanding the medium in which one moves when inhabiting a cultural-linguistic system because language is the transmitting medium in which the cultural-linguistic system is embodied. The realism entailed in Lindbeck s understanding of a community is that we are fundamentally on the receiving end when it comes to our identities whether cultural or religious. We always witness to something. Its persuasiveness rests on the fact that we never exist in an unpersuaded reality. The language of Christ is a self-sustaining and irreducible cultural-linguistic entity, which is ontologically founded upon Christ. It transmits the reality of a new being. The basic relation to the world for a Christian is that of witnessing salvation in Christ: witnessing Christ as the home of hearing the message of salvation, which is the God-willed way. Following this logic, the relation of the world and the text is one of relating to the world from the text, i.e. In Christ through the word (text) for the world, because it assumes it s logic from the way Christ ontologically relates to us.

Queued Cooperative Wireless Networks With Rateless Codes

Cooperative communication using rateless codes, in which the source transmits an infinite number of parity bits to the destination until the receipt of an acknowledgment, has recently attracted considerable interest. It provides a natural and efficient mechanism for accumulating mutual information from multiple transmitting relays. We develop an analysis of queued cooperative relay systems that combines the communication-theoretic transmission aspects of cooperative communication using rateless codes over Rayleigh fading channels with the queuing-theoretic aspects associated with buffering messages at the relays. Relay cooperation combined with queuing reduces the message transmission times and also helps distribute the traffic load in the network, which improves throughput significantly.

Performance of a pipelined ring algorithm for Fast Fourier Transform on transputer arrays

In this paper a pipelined ring algorithm is presented for efficient computation of one and two dimensional Fast Fourier Transform (FFT) on a message passing multiprocessor. The algorithm has been implemented on a transputer based system and experiments reveal that the algorithm is very efficient. A model for analysing the performance of the algorithm is developed from its computation-communication characteristics. Expressions for execution time, speedup and efficiency are obtained and these expressions are validated with experimental results obtained on a four transputer system. The analytical model is then used to estimate the performance of the algorithm for different number of processors, and for different sizes of the input data.

A Flat Concurrent Prolog compiler for PARAM

We describe a compiler for the Flat Concurrent Prolog language on a message passing multiprocessor architecture. This compiler permits symbolic and declarative programming in the syntax of Guarded Horn Rules, The implementation has been verified and tested on the 64-node PARAM parallel computer developed by C-DAC (Centre for the Development of Advanced Computing, India), Flat Concurrent Prolog (FCP) is a logic programming language designed for concurrent programming and parallel execution, It is a process oriented language, which embodies dataflow synchronization and guarded-command as its basic control mechanisms. An identical algorithm is executed on every processor in the network, We assume regular network topologies like mesh, ring, etc, Each node has a local memory, The algorithm comprises of two important parts: reduction and communication, The most difficult task is to integrate the solutions of problems that arise in the implementation in a coherent and efficient manner. We have tested the efficacy of the compiler on various benchmark problems of the ICOT project that have been reported in the recent book by Evan Tick, These problems include Quicksort, 8-queens, and Prime Number Generation, The results of the preliminary tests are favourable, We are currently examining issues like indexing and load balancing to further optimize our compiler.

Optimal control of arrivals to queues with delayed queue length information

We consider discrete-time versions of two classical problems in the optimal control of admission to a queueing system: i) optimal routing of arrivals to two parallel queues and ii) optimal acceptance/rejection of arrivals to a single queue. We extend the formulation of these problems to permit a k step delay in the observation of the queue lengths by the controller. For geometric inter-arrival times and geometric service times the problems are formulated as controlled Markov chains with expected total discounted cost as the minimization objective. For problem i) we show that when k = 1, the optimal policy is to allocate an arrival to the queue with the smaller expected queue length (JSEQ: Join the Shortest Expected Queue). We also show that for this problem, for k greater than or equal to 2, JSEQ is not optimal. For problem ii) we show that when k = 1, the optimal policy is a threshold policy. There are, however, two thresholds m(0) greater than or equal to m(1) > 0, such that mo is used when the previous action was to reject, and mi is used when the previous action was to accept.

A fault-tolerant distributed deadlock detection algorithm

In this paper, we propose a new fault-tolerant distributed deadlock detection algorithm which can handle loss of any resource release message. It is based on a token-based distributed mutual exclusion algorithm. We have evaluated and compared the performance of the proposed algorithm with two other algorithms which belong to two different classes, using simulation studies. The proposed algorithm is found to be efficient in terms of average number of messages per wait and average deadlock duration compared to the other two algorithms in all situations, and has comparable or better performance in terms of other parameters.

Damped Belief Propagation Based Near-Optimal Equalization of Severely Delay-Spread UWB MIMO-ISI Channels

In this paper, we present a belief propagation (BP) based equalizer for ultrawideband (UWB) multiple-input multiple-output (MIMO) inter-symbol interference (ISI) channels characterized by severe delay spreads. We employ a Markov random field (MRF) graphical model of the system on which we carry out message passing. The proposed BP equalizer is shown to perform increasingly closer to optimal performance for increasing number of multipath components (MPC) at a much lesser complexity than that of the optimum equalizer. The proposed equalizer performs close to within 0.25 dB of SISO AWGN performance at 10-3 bit error rate on a severely delay-spread MIMO-ISI channel with 20 equal-energy MPCs. We point out that, although MIMO/UWB systems are characterized by fully/densely connected graphical models, the following two proposed features are instrumental in achieving near-optimal performance for large number of MPCs at low complexities: i) use of pairwise compatibility functions in densely connected MRFs, and ii) use of damping of messages.

A token-based distributed algorithm for total order atomic broadcast

In this paper, we propose a new token-based distributed algorithm for total order atomic broadcast. We have shown that the proposed algorithm requires lesser number of messages compared to the algorithm where broadcast servers use unicasting to send messages to other broadcast servers. The traditional method of broadcasting requires 3(N - 1) messages to broadcast an application message, where N is the number of broadcast servers present in the system. In this algorithm, the maximum number of token messages required to broadcast an application message is 2N. For a heavily loaded system, the average number of token messages required to broadcast an application message reduces to 2, which is a substantial improvement over the traditional broadcasting approach.

A new parallel overlapped domain decomposition method for nonlinear dynamic finite element analysis

In this paper a new parallel algorithm for nonlinear transient dynamic analysis of large structures has been presented. An unconditionally stable Newmark-beta method (constant average acceleration technique) has been employed for time integration. The proposed parallel algorithm has been devised within the broad framework of domain decomposition techniques. However, unlike most of the existing parallel algorithms (devised for structural dynamic applications) which are basically derived using nonoverlapped domains, the proposed algorithm uses overlapped domains. The parallel overlapped domain decomposition algorithm proposed in this paper has been formulated by splitting the mass, damping and stiffness matrices arises out of finite element discretisation of a given structure. A predictor-corrector scheme has been formulated for iteratively improving the solution in each step. A computer program based on the proposed algorithm has been developed and implemented with message passing interface as software development environment. PARAM-10000 MIMD parallel computer has been used to evaluate the performances. Numerical experiments have been conducted to validate as well as to evaluate the performance of the proposed parallel algorithm. Comparisons have been made with the conventional nonoverlapped domain decomposition algorithms. Numerical studies indicate that the proposed algorithm is superior in performance to the conventional domain decomposition algorithms. (C) 2003 Elsevier Ltd. All rights reserved.