Exact analysis of TDMA with slot skipping

Consider a communication medium shared among a set of computer nodes; these computer nodes issue messages that are requested to be transmitted and they must finish their transmission before their respective deadlines. TDMA/SS is a protocol that solves this problem; it is a specific type of Time Division Multiple Access (TDMA) where a computer node is allowed to skip its time slot and then this time slot can be used by another computer node. We present an algorithm that computes exact queuing times for TDMA/SS in conjunction with Rate-Monotonic (RM) or Earliest- Deadline-First (EDF).

Delay-bounded medium access for unidirectional wireless links

Consider a wireless network where links may be unidirectional, that is, a computer node A can broadcast a message and computer node B will receive this message but if B broadcasts then A will not receive it. Assume that messages have deadlines. We propose a medium access control (MAC) protocol which replicates a message in time with carefully selected pauses between replicas, and in this way it guarantees that for every message at least one replica of that message is transmitted without collision. The protocol ensures this with no knowledge of the network topology and it requires neither synchronized clocks nor carrier sensing capabilities. We believe this result is significant because it is the only MAC protocol that offers an upper bound on the message queuing delay for unidirectional links without relying on synchronized clocks.

Linearizability and schedulability

Consider the problem of scheduling a set of tasks on a single processor such that deadlines are met. Assume that tasks may share data and that linearizability, the most common correctness condition for data sharing, must be satisfied. We find that linearizability can severely penalize schedulability. We identify, however, two special cases where linearizability causes no or not too large penalty on schedulability.

Preliminary discussion on globally prioritized medium access for multi-channel wireless systems

We discuss the development of a simple globally prioritized multi-channel medium access control (MAC) protocol for wireless networks. This protocol provides “hard” pre-run-time real-time guarantees to sporadic message streams, exploits a very large fraction of the capacity of all channels for “hard” real-time traffic and also makes it possible to fully utilize the channels with non real-time traffic when hard real-time messages do not request to be transmitted. The potential of such protocols for real-time applications is discussed and a schedulability analysis is also presented.

Uniprocessor EDF scheduling with mode change

Consider the problem of scheduling sporadically-arriving tasks with implicit deadlines using Earliest-Deadline-First (EDF) on a single processor. The system may undergo changes in its operational modes and therefore the characteristics of the task set may change at run-time. We consider a well-established previously published mode-change protocol and we show that if every mode utilizes at most 50% of the processing capacity then all deadlines are met. We also show that there exists a task set that misses a deadline although the utilization exceeds 50% by just an arbitrarily small amount. Finally, we present, for a relevant special case, an exact schedulability test for EDF with mode change.

The utilization bound of uniprocessor preemptive slack-monotonic scheduling is 50%

Consider the problem of scheduling a set of sporadically arriving implicit-deadline tasks to meet deadlines on a uniprocessor. Static-priority scheduling is considered using the slack-monotonic priority-assignment scheme. We prove that its utilization bound is 50%.

Schedulability analysis of generalized multiframe traffic on multihop-networks comprising software-implemented ethernet switches

Consider a multihop network comprising Ethernet switches. The traffic is described with flows and each flow is characterized by its source node, its destination node, its route and parameters in the generalized multiframe model. Output queues on Ethernet switches are scheduled by static-priority scheduling and tasks executing on the processor in an Ethernet switch are scheduled by stride scheduling. We present schedulability analysis for this setting.

Global static-priority preemptive multiprocessor scheduling with utilization bound 38%

Consider the problem of scheduling real-time tasks on a multiprocessor with the goal of meeting deadlines. Tasks arrive sporadically and have implicit deadlines, that is, the deadline of a task is equal to its minimum inter-arrival time. Consider this problem to be solved with global static-priority scheduling. We present a priority-assignment scheme with the property that if at most 38% of the processing capacity is requested then all deadlines are met.

Highly scalable aggregate computations in cyber-physical systems: physical environment meets communication protocols

In this paper, we focus on large-scale and dense Cyber- Physical Systems, and discuss methods that tightly integrate communication and computing with the underlying physical environment. We present Physical Dynamic Priority Dominance ((PD)2) protocol that exemplifies a key mechanism to devise low time-complexity communication protocols for large-scale networked sensor systems. We show that using this mechanism, one can compute aggregate quantities such as the maximum or minimum of sensor readings in a time-complexity that is equivalent to essentially one message exchange. We also illustrate the use of this mechanism in a more complex task of computing the interpolation of smooth as well as non-smooth sensor data in very low timecomplexity.

Sporadic multiprocessor scheduling with few preemptions

Consider the problem of scheduling n sporadic tasks so as to meet deadlines on m identical processors. A task is characterised by its minimum interarrival time and its worst-case execution time. Tasks are preemptible and may migrate between processors. We propose an algorithm with limited migration, configurable for a utilisation bound of 88% with few preemptions (and arbitrarily close to 100% with more preemptions).

Scheduling arbitrary-deadline sporadic task systems on multiprocessors

A new algorithm is proposed for scheduling preemptible arbitrary-deadline sporadic task systems upon multiprocessor platforms, with interprocessor migration permitted. This algorithm is based on a task-splitting approach - while most tasks are entirely assigned to specific processors, a few tasks (fewer than the number of processors) may be split across two processors. This algorithm can be used for two distinct purposes: for actually scheduling specific sporadic task systems, and for feasibility analysis. Simulation- based evaluation indicates that this algorithm offers a significant improvement on the ability to schedule arbitrary- deadline sporadic task systems as compared to the contemporary state-of-art. With regard to feasibility analysis, the new algorithm is proved to offer superior performance guarantees in comparison to prior feasibility tests.

How a cyber-physical system can efficiently obtain a snapshot of physical information even in the presence of sensor faults

We present a distributed algorithm for cyber-physical systems to obtain a snapshot of sensor data. The snapshot is an approximate representation of sensor data; it is an interpolation as a function of space coordinates. The new algorithm exploits a prioritized medium access control (MAC) protocol to efficiently transmit information of the sensor data. It scales to a very large number of sensors and it is able to operate in the presence of sensor faults.

Localizing objects in large-scale cyber- physical systems

We use the term Cyber-Physical Systems to refer to large-scale distributed sensor systems. Locating the geographic coordinates of objects of interest is an important problemin such systems. We present a new distributed approach to localize objects and events of interest in time complexity independent of number of nodes.

Perceived health in the Portuguese population aged ? 35

OBJECTIVE To evaluate the exploratory relationship between determinants of health, life satisfaction, locus of control, attitudes and behaviors and health related quality of life in an adult population. METHODS Observational study (analytical and cross-sectional) with a quantitative methodological basis. The sample was composed oy 1,214 inhabitants aged ≥ 35 in 31 civil parishes in the County of Coimbra, Portugal, 2011-2012. An anonymous and voluntary health survey was conducted, which collected the following information: demographic, clinical record, health and lifestyle behaviors; health related quality of life (Medical Outcomes Study, Short Form-36); health locus of control; survey of health attitudes and behavior, and quality of life index. Pearson’s Linear Correlation, t-Student, Wilcoxon-Mann-Whitney; One-way ANOVA; Brown-Forsythe’s F; Kruskal-Wallis; Multiple Comparisons: Tukey (HSD), Games-Howell and Conover were used in the statistical analysis. RESULTS Health related quality of life was shown to be lower in females, in older age groups, in obese/overweight individuals, widows, unassisted, those living alone, living in rural/suburban areas, those who did not work and with a medium-low socioeconomic level. Respondents with poor/very poor self-perceived health (p < 0.0001), with chronic disease (p < 0.0001), who consumed < 3 meals per day (p ≤ 0.01), who were sedentary, who slept ≤ 6 h/day and had smoked for several years revealed the worst health results. Health related quality of life was positively related with a bigger internal locus, with better health attitudes and behaviors (physical exercise, health and nutritional care, length of dependence) and with different areas of life satisfaction. CONCLUSIONS Better health related quality of life was associated with certain social, psychological, family and health characteristics, a satisfactory lifestyle, better socioeconomic conditions and a good internal locus of control over health attitudes and behaviors.

Exact admission-control for integrated aperiodic and periodic tasks

Admission controllers are used to prevent overload in systems with dynamically arriving tasks. Typically, these admission controllers are based on suÆcient (but not necessary) capacity bounds in order to maintain a low computational complexity. In this paper we present how exact admission-control for aperiodic tasks can be eÆciently obtained. Our rst result is an admission controller for purely aperiodic task sets where the test has the same runtime complexity as utilization-based tests. Our second result is an extension of the previous controller for a baseload of periodic tasks. The runtime complexity of this test is lower than for any known exact admission-controller. In addition to presenting our main algorithm and evaluating its performance, we also discuss some general issues concerning admission controllers and their implementation.