Everyone is familiar with the problem of online scheduling, even if they are not aware of it; from the way we prioritize our everyday decisions to the way a delivery service must decide on the route to follow in order to cover the ongoing requests. In computer science this is a problem of even greater importance. My thesis considers two main families of online scheduling problems in computer science, and aims to provide an extended framework for their analysis, presenting at the same time some common characteristics that connect these problems.

The first and main family of online scheduling problems considered, is task scheduling in fault-prone computing systems. As the number of clients and the possibilities offered by the rapid development of computing systems grow with time, the increase of demands of computationally intensive tasks is inevitable. Uniprocessors are no longer capable of coping with the escalation of these demands, which among others, has led to the development of multicore-based parallel machines, Internet-based computing platforms and co-operational distributed systems. Nonetheless, the challenges of these systems, even of the simplest ones, are numerous. They have to deal with continuous dynamic requests from the clients (i.e., tasks), which probably require different amount of computational resources (i.e., sizes). Processing elements (i.e., machines) may suffer from unpredictable failures, either malicious or due to overload. Furthermore, depending on the size of these systems and the exact processing units their power consumption may be of significant amount; even equal to the electricity needed for a small town. Hence limiting their power consumption is another challenge. The thesis conducts worst-case competitive analysis and covers a significant level of the three dimensions of the problem, trying to give guarantees for the performance of the algorithms used. It studies the effects of the number of machines, the number of different task sizes and the speed of the machines – which affects the power consumption of the system – on the efficiency of online scheduling algorithms. As performance measures, it uses the completed load, the pending load and the latency competitiveness of the algorithms.

The second family of problems considered, is packet scheduling over an unreliable wireless communication link. These problems have a strong connection to the task scheduling problem, especially when considering one machine and no speedup, hence some of the results can be shared. A setting with a single pair of nodes is considered, connected through an unreliable wireless channel. The sending station transmits packets to a receiving station over the channel, which can be jammed and hence corrupt the packet being transmitted. The aim of the algorithms in this case is to find the schedule that maximizes the asymptotic throughout; the long-term competitive ratio of total length of successfully transmitted packets. Then, a slightly different problem is considered, assuming infinite amount of data to be transmitted over the unreliable communication link. This time, an adversarial entity with constrained power is assumed for the channel jams. The constrained power is modeled by an Adversarial Queueing Theory (AQT) approach, defined with two main parameters; ρ, the error availability rate, and σ, the maximum batch of errors available to the adversary at any time. In this problem, the scheduling algorithms must decide on the length of the packets to be transmitted, with the objective of maximizing the goodput rate; the rate of successfully transmitted load. It is seen, that even for the simplest settings, the analysis and results are not trivial.

Key words: Online algorithms, Fault-tolerance, Energy efficiency, Task scheduling, Packet scheduling, Competitive analysis

About Elli Zavou

Elli Zavou received her B.Sc. in Computer Science from the University of Cyprus, in 2011, having a Scholarship from the Cyprus State Scholarship Foundation. She then joined IMDEA Networks Institute in Spain, and received her M.Sc. in Telematics Engineering from the Universidad Carlos III de Madrid, in 2012. Since then, she has been working towards her Ph.D. in Telematics Engineering under the supervision of Prof. Antonio Fernández Anta. She is also being supported by an FPU Grant from MECD since April 2013, until the end of her studies. Her research focuses mainly on energy efficient dynamic/online scheduling in fault-prone systems, both of non-uniform tasks in unreliable machines and of packets in unreliable communication networks.

Personal site at IMDEA Networks

Various scenes during Elli Zavou’s PhD thesis defense 

• Prof. Dr. Maria José Serna Iglesias
• Prof. Dr. Leszek Antoni Gasieniec
• Prof. Dr. Vincenzo Mancuso

University: University Carlos III of Madrid
Doctoral Program: Telematics Engineering