Computing explanations for interactive constraint-based systems

Constraint programming has emerged as a successful paradigm for modelling combinatorial problems arising from practical situations. In many of those situations, we are not provided with an immutable set of constraints. Instead, a user will modify his requirements, in an interactive fashion, until he is satisfied with a solution. Examples of such applications include, amongst others, model-based diagnosis, expert systems, product configurators. The system he interacts with must be able to assist him by showing the consequences of his requirements. Explanations are the ideal tool for providing this assistance. However, existing notions of explanations fail to provide sufficient information. We define new forms of explanations that aim to be more informative. Even if explanation generation is a very hard task, in the applications we consider, we must manage to provide a satisfactory level of interactivity and, therefore, we cannot afford long computational times. We introduce the concept of representative sets of relaxations, a compact set of relaxations that shows the user at least one way to satisfy each of his requirements and at least one way to relax them, and present an algorithm that efficiently computes such sets. We introduce the concept of most soluble relaxations, maximising the number of products they allow. We present algorithms to compute such relaxations in times compatible with interactivity, achieving this by indifferently making use of different types of compiled representations. We propose to generalise the concept of prime implicates to constraint problems with the concept of domain consequences, and suggest to generate them as a compilation strategy. This sets a new approach in compilation, and allows to address explanation-related queries in an efficient way. We define ordered automata to compactly represent large sets of domain consequences, in an orthogonal way from existing compilation techniques that represent large sets of solutions.

The protection and security of vulnerable populations in complex emergencies using the Dadaab refugee camps in the north eastern province of Kenya as a case study

The past two decades has seen a dramatic upheaval in the international world order: the end of the Cold War, the 9/11 attacks and the subsequent 'War on Terror', increased Jihadist activities, the accelerated pace of globalization, climate change and the 2008 global financial crisis have contributed to fear, uncertainty, poverty, conflict, massive displacements of populations of asylum seekers and refugees globally and a proliferation of Protracted Refugee Situations (PRS), defined as situations in which refugees have been in exile 'for 5 years or more after their initial displacement, without immediate prospects for implementation of durable solutions. In the past two decades there has been a huge proliferation of these with more than 7.2 million refugees now trapped in these PRS, with a further 16 million internally displaced persons (IDPs) trapped in camps within their own countries. The Dadaab refugee complex in Kenya, which of as March 2012, holds over 463,000 refugees, is the most significant and extreme example in recent times of a PRS. It was established in 1991 following the collapse of the Somali Government of Dictator Siad Barre, and the disintegration of Somalia into the chaos that still exists today. PRS such as Dadaab raise particular issues about humanitarianism in terms of aid, protection, security, human rights and the actions (or inaction) of the various stakeholders on an international, national and local level. This thesis investigates these issues by the use of a case study methodology on Dadaab as a PRS, framed in the context of humanitarianism and in particular the issues that arise in terms of how the international community, the UN system and individual states provide assistance and protection to vulnerable populations. Although the refugee camps have been in existence (as of 2012) for over 20 years, there has never been such a detailed study of Dadaab (or any other PRS) undertaken to date and would be of interest to academics in the areas of international relations, refugee/migration studies and global Governance as well as practitioners in both humanitarian response and development

Identifying sources of global contention in constraint satisfaction search

Much work has been done on learning from failure in search to boost solving of combinatorial problems, such as clause-learning and clause-weighting in boolean satisfiability (SAT), nogood and explanation-based learning, and constraint weighting in constraint satisfaction problems (CSPs). Many of the top solvers in SAT use clause learning to good effect. A similar approach (nogood learning) has not had as large an impact in CSPs. Constraint weighting is a less fine-grained approach where the information learnt gives an approximation as to which variables may be the sources of greatest contention. In this work we present two methods for learning from search using restarts, in order to identify these critical variables prior to solving. Both methods are based on the conflict-directed heuristic (weighted-degree heuristic) introduced by Boussemart et al. and are aimed at producing a better-informed version of the heuristic by gathering information through restarting and probing of the search space prior to solving, while minimizing the overhead of these restarts. We further examine the impact of different sampling strategies and different measurements of contention, and assess different restarting strategies for the heuristic. Finally, two applications for constraint weighting are considered in detail: dynamic constraint satisfaction problems and unary resource scheduling problems.

Hardware design of cryptographic accelerators

With the rapid growth of the Internet and digital communications, the volume of sensitive electronic transactions being transferred and stored over and on insecure media has increased dramatically in recent years. The growing demand for cryptographic systems to secure this data, across a multitude of platforms, ranging from large servers to small mobile devices and smart cards, has necessitated research into low cost, flexible and secure solutions. As constraints on architectures such as area, speed and power become key factors in choosing a cryptosystem, methods for speeding up the development and evaluation process are necessary. This thesis investigates flexible hardware architectures for the main components of a cryptographic system. Dedicated hardware accelerators can provide significant performance improvements when compared to implementations on general purpose processors. Each of the designs proposed are analysed in terms of speed, area, power, energy and efficiency. Field Programmable Gate Arrays (FPGAs) are chosen as the development platform due to their fast development time and reconfigurable nature. Firstly, a reconfigurable architecture for performing elliptic curve point scalar multiplication on an FPGA is presented. Elliptic curve cryptography is one such method to secure data, offering similar security levels to traditional systems, such as RSA, but with smaller key sizes, translating into lower memory and bandwidth requirements. The architecture is implemented using different underlying algorithms and coordinates for dedicated Double-and-Add algorithms, twisted Edwards algorithms and SPA secure algorithms, and its power consumption and energy on an FPGA measured. Hardware implementation results for these new algorithms are compared against their software counterparts and the best choices for minimum area-time and area-energy circuits are then identified and examined for larger key and field sizes. Secondly, implementation methods for another component of a cryptographic system, namely hash functions, developed in the recently concluded SHA-3 hash competition are presented. Various designs from the three rounds of the NIST run competition are implemented on FPGA along with an interface to allow fair comparison of the different hash functions when operating in a standardised and constrained environment. Different methods of implementation for the designs and their subsequent performance is examined in terms of throughput, area and energy costs using various constraint metrics. Comparing many different implementation methods and algorithms is nontrivial. Another aim of this thesis is the development of generic interfaces used both to reduce implementation and test time and also to enable fair baseline comparisons of different algorithms when operating in a standardised and constrained environment. Finally, a hardware-software co-design cryptographic architecture is presented. This architecture is capable of supporting multiple types of cryptographic algorithms and is described through an application for performing public key cryptography, namely the Elliptic Curve Digital Signature Algorithm (ECDSA). This architecture makes use of the elliptic curve architecture and the hash functions described previously. These components, along with a random number generator, provide hardware acceleration for a Microblaze based cryptographic system. The trade-off in terms of performance for flexibility is discussed using dedicated software, and hardware-software co-design implementations of the elliptic curve point scalar multiplication block. Results are then presented in terms of the overall cryptographic system.

The impact of saving and credit cooperatives on food security in the West Amhara Region of Ethiopia

In rural Ethiopia, among other things, lack of adequate financial service is considered as the basic problem to alleviate rural poverty and to solve the problem of food insecurity. Commercial banks are restricted to urban centres. Providing rural financial service through RUSACCO to the poor has been proposed as a tool for economic development and for achieving food security. Evidence from research in this regard has been so far scanty, especially in rural Ethiopia. The aims of this study are to analyze the determinants of membership, to identify socioeconomic and demographic factors that influence members’ participation in RUSACCOs and to quantify the impact of RUSACCOs on member households’ food security. The study was conducted in two purposely selected woredas in the Amhara region one from food insecure (Lay Gayint woreda) and the other from food secure (Dejen woreda). Six RUSACCOs were selected randomly from these two woredas. Both qualitative and quantitative data were collected. Key informant interviews, focus group discussions and survey techniques were used to collect primary data. Collected data was then analyzed using mixed methods depending on the nature of data. For quantitative data analysis appropriate statistical models were used. The study result reveals that the number of members in each RUSACCO is very small. However, the majority of non-member respondents are willing to join RUSACCO. Lack of information about the benefits of RUSACCO membership is the main problem why many rural poor do not join RUSACCOs. Members participate in different aspects of the cooperatives, starting from attending general assembly up to board membership. They also participate actively in saving and borrowing activities of RUSACCO. The majority of the respondents believe the RUSACCO is a vital instrument in combating food insecurity. The empirical findings indicate that gender, marital status, occupation, educational level, participation in local leadership and participation in other income generation means determine the decision of rural poor to join a RUSACCO or not. The amount of saving is determined by household head occupation, farming experience and income level. While age of household head, primary occupation, farming experience, date of membership, annual total consumption expenditure, amount of saving and participation in other income generation activities influence members’ amount of borrowing by RUSACCO members. Finally, the study confirms that RUSACCO participation improves household food security. RUSACCO membership has made positive impact on household total consumption expenditure and food expenditure.