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.

Strike Hard, Strike Sure - Operation Musketeer : British Military Planning during the Suez Crisis, 1956

This study analyses British military planning and actions during the Suez Crisis in 1956. It seeks to find military reasons for the change of concepts during the planning and compares these reasons with the tactical doctrines of the time. The thesis takes extensive advantage of military documents preserved in the National Archives, London. In order to expand the understanding of the exchange of views during the planning process, the private papers of high ranking military officials have also been consulted. French military documents preserved in the Service Historique de la Defence, Paris, have provided an important point of comparison. The Suez Crisis caught the British armed forces in the middle of a transition phase. The main objective of the armed forces was to establish a credible deterrence against the Soviet Union. However, due to overseas commitments the Middle East playing a paramount role because of its economic importance the armed forces were compelled to also prepare for Limited War and the Cold War. The armed forces were not fully prepared to meet this demand. The Middle Eastern garrison was being re-organised after the withdrawal from the Canal Base and the concept for a strategic reserve was unimplemented. The tactical doctrines of the time were based on experiences from the Second World War. As a result, the British view of amphibious operations and the subsequent campaigns emphasised careful planning, mastery of the sea and the air, sufficient superiority in numbers and firepower, centralised command and extensive administrative preparations. The British military had realized that Nasser could nationalise the Suez Canal and prepared an outline plan to meet this contingency. Although the plan was nothing more than a concept, it was accepted as a basis for further planning when the Canal was nationalised at the end of July. This plan was short-lived. The nominated Task Force Commanders shifted the landing site from Port Said to Alexandria because it enabled faster expansion of the bridgehead. In addition, further operations towards Cairo the hub of Nasser s power would be easier to conduct. The operational concept can be described as being traditional and was in accordance with the amphibious warfare doctrine. This plan was completely changed at the beginning of September. Apparently, General Charles Keightley, the Commander-in-Chief, and the Chairman of the Chiefs of Staff Committee developed the idea of prolonged aerial operations. The essence of the concept was to break the Egyptian will to resist by attacking the oil facilities, the transportation system and the armed forces. This victory through air concept would be supported by carefully planned psychological operations. This concept was in accordance with the Royal Air Force doctrine, which promoted a bomber offensive against selected target categories. General Keightley s plan was accepted despite suspicions at every planning level. The Joint Planning Staff and the Task Force Commanders opposed the concept from the beginning to the end because of its unpredictability. There was no information that suggested the bombing would persuade the Egyptians to submit. This problem was worsened by the fact that British intelligence was unable to provide reliable strategic information. The Task Force Commanders, who were responsible for the tactical plans, were not able to change Keightley s mind, but the concept was expanded to include a traditional amphibious assault on Port Said due to their resistance. The bombing campaign was never tested as the Royal Air Force was denied authorisation to destroy the transportation and oil targets. The Chiefs of Staff and General Keightley were too slow to realise that the execution of the plan depended on the determination of the Prime Minister. However, poor health, a lack of American and domestic support and the indecisiveness of the military had ruined Eden s resolve. In the end, a very traditional amphibious assault, which was bound to succeed at the tactical level but fail at the strategic level, was launched against Port Said.

Adenoviral gene therapy for non-small cell lung cancer

Adenoviral gene therapy is an experimental approach to cancer refractory to standard cancer therapies. Adenoviruses can be utilized as vectors to deliver therapeutic transgenes into cancer cells, while gene therapy with oncolytic adenoviruses exploits the lytic potential of viruses to kill tumor cells. Although adenoviruses demonstrate several advantages over other vectors - such as the unparalleled transduction efficacy and natural tropism to a wide range of tissues - the gene transfer efficacy to cancer cells has been limited, consequently restricting the therapeutic effect. There are, however, several approaches to circumvent this problem. We utilized different modified adenoviruses to obtain information on adenovirus tropism towards non-small cell lung cancer (NSCLC) cells. To enhance therapeutic outcome, oncolytic adenoviruses were evaluated. Further, to enhance gene delivery to tumors, we used mesenchymal stem cells (MSCs) as carriers. To improve adenovirus specificity, we investigated whether widely used cyclooxygenase 2 (Cox-2) promoter is induced by adenovirus infection in nontarget cells and whether selectivity can be retained by the 3 untranslated region (UTR) AU-rich elements. In addition, we investigated whether switching adenovirus fiber can retain gene delivery in the presence of neutralizing antibodies. Our results show that adenoviruses, whose capsids were modified with arginine-glycine-aspartatic acid (RGD-4C), the serotype 3 knob, or polylysins displayed enhanced gene transfer into NSCLC cell lines and fresh clinical specimens from patients. The therapeutic efficacy was further improved by using respective oncolytic adenoviruses with isogenic 24bp deletion in the E1A gene. Cox-2 promoter was also shown to be induced in normal and tumor cells following adenovirus infection, but utilization of 3 UTR elements can increase the tumor specificity of the promoter. Further, the results suggested that use of MSCs could enhance the bioavailability and delivery of adenoviruses into human tumors, although cells had no tumor tropism per se. Finally, we demonstrated that changing adenovirus fiber can allow virus to escape from existing neutralizing antibodies when delivered systemically. In conclusion, these results reveal that adenovirus gene transfer and specificity can be increased by using modified adenoviruses and MSCs as carriers, and fiber modifications simultaneously decrease the effect of neutralizing antibodies. This promising data suggest that these approaches could translate into clinical testing in patients with NSCLC refractory to current modalities.

Debunking Weak Sustainable Consumption : Towards Strong Sustainable Consumption Governance

Achieving sustainable consumption patterns is a crucial step on the way towards sustainability. The scientific knowledge used to decide which priorities to set and how to enforce them has to converge with societal, political, and economic initiatives on various levels: from individual household decision-making to agreements and commitments in global policy processes. The aim of this thesis is to draw a comprehensive and systematic picture of sustainable consumption and to do this it develops the concept of Strong Sustainable Consumption Governance. In this concept, consumption is understood as resource consumption. This includes consumption by industries, public consumption, and household consumption. Next to the availability of resources (including the available sink capacity of the ecosystem) and their use and distribution among the Earth’s population, the thesis also considers their contribution to human well-being. This implies giving specific attention to the levels and patterns of consumption. Methods: The thesis introduces the terminology and various concepts of Sustainable Consumption and of Governance. It briefly elaborates on the methodology of Critical Realism and its potential for analysing Sustainable Consumption. It describes the various methods on which the research is based and sets out the political implications a governance approach towards Strong Sustainable Consumption may have. Two models are developed: one for the assessment of the environmental relevance of consumption activities, another to identify the influences of globalisation on the determinants of consumption opportunities. Results: One of the major challenges for Strong Sustainable Consumption is that it is not in line with the current political mainstream: that is, the belief that economic growth can cure all our problems. So, the proponents have to battle against a strong headwind. Their motivation however is the conviction that there is no alternative. Efforts have to be taken on multiple levels by multiple actors. And all of them are needed as they constitute the individual strings that together make up the rope. However, everyone must ensure that they are pulling in the same direction. It might be useful to apply a carrot and stick strategy to stimulate public debate. The stick in this case is to create a sense of urgency. The carrot would be to articulate better the message to the public that a shrinking of the economy is not as much of a disaster as mainstream economics tends to suggest. In parallel to this it is necessary to demand that governments take responsibility for governance. The dominant strategy is still information provision. But there is ample evidence that hard policies like regulatory instruments and economic instruments are most effective. As for Civil Society Organizations it is recommended that they overcome the habit of promoting Sustainable (in fact green) Consumption by using marketing strategies and instead foster public debate in values and well-being. This includes appreciating the potential of social innovation. A countless number of such initiatives are on the way but their potential is still insufficiently explored. Beyond the question of how to multiply such approaches, it is also necessary to establish political macro structures to foster them.

Small State Cultures of Consensus : State Traditions and Consensus-Seeking in the Neo-Corporatist and Neutrality Policies in Post-1945 Austria and Finland

Austria and Finland are persistently referred to as the “success stories” of post-1945 European history. Notwithstanding their different points of departure, in the course of the Cold War both countries portrayed themselves as small and neutral border-states in the world dictated by superpower politics. By the 1970s, both countries frequently ranked at the top end in various international classifications regarding economic development and well-being in society. This trend continues today. The study takes under scrutiny the concept of consensus which figures centrally in the two national narratives of post-1945 success. Given that the two domestic contexts as such only share few direct links with one another and are more obviously different than similar in terms of their geographical location, historical experiences and politico-cultural traditions, the analogies and variations in the anatomies of the post-1945 “cultures of consensus” provide an interesting topic for a historical comparative and cross-national examination. The main research question concerns the identification and analysis of the conceptual and procedural convergence points of the concepts of the state and consensus. The thesis is divided into six main chapters. After the introduction, the second chapter presents the theoretical framework in more detail by focusing on the key concepts of the study – the state and consensus. Chapter two also introduces the comparative historical and cross-national research angles. Chapter three grounds the key concepts of the state and consensus in the historical contexts of Austria and Finland by discussing the state, the nation and democracy in a longer term comparative perspective. The fourth and fifth chapter present case studies on the two policy fields, the “pillars”, upon which the post-1945 Austrian and Finnish cultures of consensus are argued to have rested. Chapter four deals with neo-corporatist features in the economic policy making and chapter five discusses the building up of domestic consensus regarding the key concepts of neutrality policies in the 1950s and 1960s. The study concludes that it was not consensus as such but the strikingly intense preoccupation with the theme of domestic consensus that cross-cut, in a curiously analogous manner, the policy-making processes studied. The main challenge for the post-1945 architects of Austrian and Finnish cultures of consensus was to find strategies and concepts for consensus-building which would be compatible with the principles of democracy. Discussed at the level of procedures, the most important finding of the study concerns the triangular mechanism of coordination, consultation and cooperation that set into motion and facilitated a new type of search for consensus in both post-war societies. In this triangle, the agency of the state was central, though in varying ways. The new conceptions concerning a small state’s position in the Cold War world also prompted cross-nationally perceivable willingness to reconsider inherited concepts and procedures of the state and the nation. At the same time, the ways of understanding the role of the state and its relation to society remained profoundly different in Austria and Finland and this basic difference was in many ways reflected in the concepts and procedures deployed in the search for consensus and management of domestic conflicts. For more detailed information, please consult the author.

The Macroeconomic Effects of Fiscal Policy in a Small Open Economy under a Flexible Exchange Rate Regime

This licentiate's thesis analyzes the macroeconomic effects of fiscal policy in a small open economy under a flexible exchange rate regime, assuming that the government spends exclusively on domestically produced goods. The motivation for this research comes from the observation that the literature on the new open economy macroeconomics (NOEM) has focused almost exclusively on two-country global models and the analyses of the effects of fiscal policy on small economies are almost completely ignored. This thesis aims at filling in the gap in the NOEM literature and illustrates how the macroeconomic effects of fiscal policy in a small open economy depend on the specification of preferences. The research method is to present two theoretical model that are extensions to the model contained in the Appendix to Obstfeld and Rogoff (1995). The first model analyzes the macroeconomic effects of fiscal policy, making use of a model that exploits the idea of modelling private and government consumption as substitutes in private utility. The model offers intuitive predictions on how the effects of fiscal policy depend on the marginal rate of substitution between private and government consumption. The findings illustrate that the higher the substitutability between private and government consumption, (i) the bigger is the crowding out effect on private consumption (ii) and the smaller is the positive effect on output. The welfare analysis shows that the less fiscal policy decreases welfare the higher is the marginal rate of substitution between private and government consumption. The second model of this thesis studies how the macroeconomic effects of fiscal policy depend on the elasticity of substitution between traded and nontraded goods. This model reveals that this elasticity a key variable to explain the exchange rate, current account and output response to a permanent rise in government spending. Finally, the model demonstrates that temporary changes in government spending are an effective stabilization tool when used wisely and timely in response to undesired fluctuations in output. Undesired fluctuations in output can be perfectly offset by an opposite change in government spending without causing any side-effects.