Shared communication media are widely used in many applications including safety-critical applications. However, noise and transient errors can cause transmission failures. We consider the problem of designing and minimizing the length of fault-tolerant static schedules for transmitting messages in these media provided the number of errors fall below some upper bound. To transmitnmessages in a medium while tolerating a maximum offfaults, prior work had shown how to construct schedules which had a fault tolerance overhead ofnf/2. In this paper, we provide an efficient constructive algorithm for producing a schedule for n messages with total lengthn+O(f2log2n) that can toleratefmedium errors. We also provide an algorithm for randomly generating fault-tolerant schedules with lengthn+O(flog(f) log(n)) as well as a technique for quickly verifying these on reasonably small inputs.

We consider the problem of load-balancing on distributed databases. We assume that data is divided into chunks and each chunk can be replicated on a constant number d of servers. When a request arrives, it is routed to one of the servers that contains the relevant chunk. Each server may store outstanding requests in a bounded queue and requests may be rejected if the queue is full. The goal is to design strategies for data distribution and request routing that minimize both the rejection rate and the average request latency.

Distributed storage systems are used widely in clouds, databases, and file systems. These systems store a large amount of data across multiple servers. When a request to access data comes in, it is routed to the appropriate server, queued, and eventually processed. If the server's queue is full, then requests may be rejected. Thus, one important challenge when designing the algorithm for allocating data to servers is the fact that the request pattern may be unbalanced, unpredictable, and may change over time. If some servers get a large fraction of the requests, they are overloaded, leading to many rejects. In this paper, we analyze this problem theoretically under adversarial assumptions. In particular, we assume that the request sequence is generated by an adversarial process to maximize the number of rejects and analyze the performance of various algorithmic strategies in terms of the fraction of the requests rejected. We show that no deterministic strategy can perform well. On the other hand, a simple randomized strategy guarantees that at most a constant fraction of requests are rejected in expectation. We also show that moving data to load balance is essential if we want to reject a very small fraction (1/m where m is the number of servers) of requests. We design a strategy with randomization and data transfer to achieve this performance with speed augmentation. Finally, we conduct experiments and show that our algorithms perform well in practice.

Shared communication media are widely used in many applications including safety critical applications such as control systems on flights or autonomous vehicles. Noise and transient errors can cause transmission failures. We consider the problem of designing fault tolerant static schedules for transmitting messages in these media. In particular, we assume that the schedule of transmission over all messages must be computed in advance and must guarantee that all messages will be delivered as long as the number of medium errors falls below a provided upper bound, regardless of when the medium errors occur. It is crucial that the messages be delivered in a timely manner, and hence we are interested in minimizing the length of the schedule that achieves the desired level of fault tolerance. In this paper, we provide an efficient algorithm for producing a schedule for n messages with total length n + O(f2log2n) that can tolerate f medium errors. We also prove that fault-tolerant schedules with length n+O(f logf logn) exist. Since n steps are required to transmit n messages, the overhead of fault tolerance is characterized by the additive terms of O(f2log2n) and O(f logf logn), respectively. Both of these terms are sublinear in n and represent asymptotic improvements to the previously best known schedule, which has overhead fn/2.

Modern parallel platforms, such as clouds or servers, are often shared among many different jobs. However, existing parallel programming runtime systems are designed and optimized for running a single parallel job, so it is generally hard to directly use them to schedule multiple parallel jobs without incurring high overhead and inefficiency. In this work, we develop AMCilk (Adaptive Multiprogrammed Cilk), a novel runtime system framework, designed to support multiprogrammed parallel workloads. AMCilk has client-server architecture where users can dynamically submit parallel jobs to the system. AMCilk has a single runtime system that runs these jobs while dynamically reallocating cores, last-level cache, and memory bandwidth among these jobs according to the scheduling policy. AMCilk exposes the interface to the system designer, which allows the designer to easily build different scheduling policies meeting the requirements of various application scenarios and performance metrics, while AMCilk transparently (to designers) enforces the scheduling policy. The primary feature of AMCilk is the low-overhead and responsive preemption mechanism that allows fast reallocation of cores between jobs. Our empirical evaluation indicates that AMCilk incurs small overheads and provides significant benefits on application-specific criteria for a set of 4 practical applications due to its fast and low-overhead core reallocation mechanism.