On the Complexity of Universal Leader Election

Electing a leader is a fundamental task in distributed computing. In its implicit version, only the leader must know who is the elected leader. This paper focuses on studying the message and time complexity of randomized implicit leader election in synchronous distributed networks. Surprisingly, the most "obvious" complexity bounds have not been proven for randomized algorithms. The "obvious" lower bounds of O(m) messages (m is the number of edges in the network) and O(D) time (D is the network diameter) are non-trivial to show for randomized (Monte Carlo) algorithms. (Recent results that show that even O(n) (n is the number of nodes in the network) is not a lower bound on the messages in complete networks, make the above bounds somewhat less obvious). To the best of our knowledge, these basic lower bounds have not been established even for deterministic algorithms (except for the limited case of comparison algorithms, where it was also required that some nodes may not wake up spontaneously, and that D and n were not known).

We establish these fundamental lower bounds in this paper for the general case, even for randomized Monte Carlo algorithms. Our lower bounds are universal in the sense that they hold for all universal algorithms (such algorithms should work for all graphs), apply to every D, m, and n, and hold even if D, m, and n are known, all the nodes wake up simultaneously, and the algorithms can make anyuse of node's identities. To show that these bounds are tight, we present an O(m) messages algorithm. An O(D) time algorithm is known. A slight adaptation of our lower bound technique gives rise to an O(m) message lower bound for randomized broadcast algorithms.

An interesting fundamental problem is whether both upper bounds (messages and time) can be reached simultaneously in the randomized setting for all graphs. (The answer is known to be negative in the deterministic setting). We answer this problem partially by presenting a randomized algorithm that matches both complexities in some cases. This already separates (for some cases) randomized algorithms from deterministic ones. As first steps towards the general case, we present several universal leader election algorithms with bounds that trade-off messages versus time. We view our results as a step towards understanding the complexity of universal leader election in distributed networks.

Scalable black-box prediction models for multi-dimensional adaptation on NUMA multi-cores

This paper presents a scalable, statistical ‘black-box’ model for predicting the performance of parallel programs on multi-core non-uniform memory access (NUMA) systems. We derive a model with low overhead, by reducing data collection and model training time. The model can accurately predict the behaviour of parallel applications in response to changes in their concurrency, thread layout on NUMA nodes, and core voltage and frequency. We present a framework that applies the model to achieve significant energy and energy-delay-square (ED2) savings (9% and 25%, respectively) along with performance improvement (10% mean) on an actual 16-core NUMA system running realistic application workloads. Our prediction model proves substantially more accurate than previous efforts.

Lightweight Risk Management in Agile projects

Risk management in software engineering has become a recognized project management practice but it seems that not all companies are systematically applying it. At the same time, agile methods have become popular, partly because proponents claim that agile methods implicitly reduce risks due
to, for example, more frequent and earlier feedback, shorter periods of development time and easier prediction of cost. Therefore, there is a need to investigate how risk management can be usable in iterative and evolutionary software development processes. This paper investigates the gathering of empirical data on risk management from the project environment and presents
a novel approach to manage risk in agile projects. Our approach is based on a prototype tool, Agile Risk Tool (ART). This tool reduces human effort in risk management by using software agents to identify, assess and monitor risk, based on input and data collected from the project environment and by applying
some designated rules. As validation, groups of student project data were used to provide evidence of the efficacy of this approach. We demonstrate the approach and the feasibility of using a lightweight risk management tool to alert, assess and monitor risk with reduced human effort.

Behavioral Model Generation from Use Cases Based on Ontology Mapping and GRASP Patterns

This paper contributes a new approach for developing UML software designs from Natural Language (NL), making use of a meta-domain oriented ontology, well established software design principles and Natural Language Processing (NLP) tools. In the approach described here, banks of grammatical rules are used to assign event flows from essential use cases. A domain specific ontology is also constructed, permitting semantic mapping between the NL input and the modeled domain. Rules based on the widely-used General Responsibility Assignment Software Principles (GRASP) are then applied to derive behavioral models.

'Whatever You Say, Say Nothing' : Researching Memory & Identity in Mid-Ulster, 1945-1969

The influence of collective memory on political identity in Ireland has been well documented. It has particular force in Northern Ireland where there is fundamental disagreement about how and why the conflict erupted and how it should be resolved. This article outlines some of the issues encountered by an ‘insider’ when attempting to record and analyse the conflicting memories of a range of Protestants and Catholics who grew up in Mid-Ulster in the decades preceding the Troubles. In particular, it considers the challenges and opportunities presented by a two-pronged approach to oral history: using testimony as evidence about historical experience in the past and as evidence about historical memory – both collective and individual – in the present.

Design patterns percolating to parallel programming framework implementation

Structured parallel programming is recognised as a viable and effective means of tackling parallel programming problems. Recently, a set of simple and powerful parallel building blocks RISC pb²l) has been proposed to support modelling and implementation of parallel frameworks. In this work we demonstrate how that same parallel building block set may be used to model both general purpose parallel programming abstractions, not usually listed in classical skeleton sets, and more specialized domain specific parallel patterns. We show how an implementation of RISC pb² l can be realised via the FastFlow framework and present experimental evidence of the feasibility and efficiency of the approach.

SHEPARD: Scheduling on heterogeneous platforms using application resource demands

Heterogeneous computing technologies, such as multi-core CPUs, GPUs and FPGAs can provide significant performance improvements. However, developing applications for these technologies often results in coupling applications to specific devices, typically through the use of proprietary tools. This paper presents SHEPARD, a compile time and run-time framework that decouples application development from the target platform and enables run-time allocation of tasks to heterogeneous computing devices. Through the use of special annotated functions, called managed tasks, SHEPARD approximates a task's performance on available devices, and coupled with the approximation of current device demand, decides which device can satisfy the task with the lowest overall execution time. Experiments using a task parallel application, based on an in-memory database, demonstrate the opportunity for automatic run-time task allocation to achieve speed-up over a static allocation to a single specific device. © 2014 IEEE.

Cost-Directed Refactoring for Parallel Erlang Programs

This paper presents a new programming methodology for introducing and tuning parallelism in Erlang programs, using source-level code refactoring from sequential source programs to parallel programs written using our skeleton library, Skel. High-level cost models allow us to predict with reasonable accuracy the parallel performance of the refactored program, enabling programmers to make informed decisions about which refactorings to apply. Using our approach, we demonstrate easily obtainable, significant and scalable speedups of up to 21 on a 24-core machine over the sequential code.

Water and temperature relations of soil Actinobacteria

Actinobacteria perform essential functions within soils, and are dependent on available water to do so. We determined the water-activity (a_w) limits for cell division of Streptomyces albidoflavus, Streptomyces rectiviolaceus, Micromonospora grisea and Micromonospora (JCM 3050) over a range of temperatures, using culture media supplemented with a biologically permissive solute (glycerol). Each species grew optimally at 0.998 a_w (control; no added glycerol) and growth rates were near-optimal in the range 0.971–0.974 (1 M glycerol) at permissive temperatures. Each was capable of cell division at 0.916–0.924 a_w (2 M glycerol), but only S. albidoflavus grew at 0.895 or 0.897 a_w (3 M glycerol, at 30 and 37°C respectively). For S. albidoflavus, however, no growth occurred on media at ≤ 0.870 (4 M glycerol) during the 40-day assessment period, regardless of temperature, and a theoretical limit of 0.877 a_w was derived by extrapolation of growth curves. This level of solute tolerance is high for non-halophilic bacteria, but is consistent with reported limits for the growth and metabolic activities of soil microbes. The limit, within the range 0.895–0.870 a_w, is very much inferior to those for obligately halophilic bacteria and extremely halophilic or xerophilic fungi, and is inconsistent with earlier reports of cell division at 0.500 a_w. These findings are discussed in relation to planetary protection policy for space exploration and the microbiology of arid soils.