- S. Kashyap, S. Deb, K.V.M. Naidu, R. Rastogi
and A. Srinivasan. Efficient Gossip-Based
to appear in
ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems
Abstract: There has been a growing interest in
gossip-based protocols that employ randomized communication to ensure
robust information dissemination. In this paper we present a novel
gossip-based scheme using which all nodes in an n-node overlay network
can compute the common aggregates of MIN, MAX, SUM, AVERAGE and RANK of
using O(n loglog n) messages in O(log n loglog n) rounds of communication.
To the best of ours knowledge, ours is the first result that shows how to
compute these aggregates with high probability using only O(n loglog n)
messages. In contrast, the best known gossip-based algorithm for computing
these aggregates requires O(n log n) messages and O(log n) rounds. Thus,
our algorithm allows system designers to trade off a small increase in
round complexity with a significant reduction in message complexity. This
can lead to dramatically lower network congestion and longer node
lifetimes in wireless and sensor networks, where channel bandwidth and
battery life are severely constrained.
- J. Anderson, A. Block and A. Srinivasan.
Quick Release Fair Scheduling,
Proceedings of the 24th IEEE Real-time Systems
Symposium, pages 130-141, 2003.
In prior work on multiprocessor fairness, efficient techniques with
provable properties for reallocating spare processing capacity have been
elusive. In this paper, we address this shortcoming by proposing a new
notion of multiprocessor fairness, called quick-release fair (QRfair)
scheduling, which is a derivative of Pfair scheduling that allows
efficient allocation of spare capacity. Under QRfair scheduling, each
task is specified by giving both a minimum and a maximum weight (i.e.,
processor share). The goal is to schedule each task (as the available
spare capacity changes) at a rate that is (i) at least that implied by
its minimum weight and (ii) at most that implied by its maximum weight.
Our contributions are fourfold. First, we present a quick-release
variant of the PD2 Pfair scheduling algorithm called PDQ. Second, we
formally prove that the allocations of PDQ always satisfy (i) and (ii).
Third, we consider the problem of defining maximum weights in a way that
encourages a fair distribution of spare capacity. Fourth, we present
results from extensive simulation experiments that show the efficacy of
PDQ in allocating spare capacity.
- A. Srinivasan and J. Anderson
Efficient Scheduling of Soft Real-time Applications on Multiprocessors,
Real-time Applications on Multiprocessors, Proceedings of the 15th
Euromicro Conference on Real-Time Systems,
pages 51-59, July 2003. (A journal version
of this paper has
appeared in Journal of Embedded Computing, Volume 1,
Number 2, pages 285-302, 2005.)
In soft real-time applications, tasks are allowed to miss their
deadlines. Thus, less-costly scheduling algorithms can be used at the
price of occasional violations of timing constraints. This may be
acceptable if reasonable tardiness bounds (i.e., bounds on the extent to
which deadlines may be missed) can be guaranteed.
In this paper, we
consider soft real-time applications implemented on multiprocessors.
Pfair scheduling algorithms are the only known means of optimally
scheduling hard real-time applications on multiprocessors. For this
reason, we consider the use of such algorithms here. In the design of
Pfair scheduling algorithms, devising schemes to correctly break ties
when several tasks have the same deadline is a critical issue. Such
tie-breaking schemes entail overhead that may be unacceptable or
unnecessary in soft real-time applications. In this paper, we consider
the earliest pseudo-deadline first (EPDF) Pfair algorithm, which avoids
this overhead by using no tie-breaking information. Our main
contributions are twofold. First, we establish a condition for ensuring
a tardiness of at most one quantum under EPDF. This condition is very
liberal and should often hold in practice. Second, we present simulation
results involving randomly-generated task sets, including those that do
not satisfy our condition. In these experiments, deadline misses rarely
occurred, and no misses by more than one quantum ever occurred.
- A. Srinivasan and J. Anderson.
Fair Scheduling of Dynamic Task Systems on Multiprocessors,
Proceedings of the 11th International Workshop on Parallel and Distributed Real-Time
Systems, held in conjunction with the International Parallel and
Distributed Processing Symposium, April 2003. (A
of this paper has appeared in Journal of
Systems and Software, Volume 77, Number 1, pages 67-80, April
In dynamic real-time task systems, tasks that are subject to deadlines
are allowed to join and leave the system. In previous work, Stoica et
al. and Baruah et al. presented conditions under which such joins and
leaves may occur in fair-scheduled uniprocessor systems without causing
missed deadlines. In this paper, we extend their work by considering
fair-scheduled multiprocessors. We show that their conditions are
sufficient on M processors, under all known (dynamic-priority) Pfair
scheduling algorithms, if the utilization of every subset of M-1 tasks
is at most one. Further, for the general case in which task utilizations
are not restricted in this way, we derive sufficient join/leave
conditions for the PD2 Pfair algorithm. We also show that, in general,
these conditions cannot be improved upon without causing missed
- A. Srinivasan, P. Holman, J. Anderson, and S. Baruah.
The Case for Fair Multiprocessor Scheduling,
Proceedings of the 11th International
Workshop on Parallel and Distributed Real-Time Systems, held in
conjunction with the International Parallel and Distributed Processing
Symposium, April 2003.
Partitioning and global scheduling are two approaches for scheduling
real-time tasks on multiprocessors. Though partitioning is sub-optimal,
it has traditionally been preferred; this is mainly due to the fact that
well-understood uniprocessor scheduling algorithms can be used on each
processor. In recent years, global-scheduling algorithms based on the
concept of proportionate fairness (Pfairness) have received considerable
attention. Pfair algorithms are of interest because they are currently
the only known method for optimally scheduling periodic, sporadic, and
rate-based task systems on multiprocessors. In addition, there has been
growing practical interest in scheduling with fairness guarantees.
However, the frequency of context switching and migration in
Pfair-scheduled systems has led to some questions concerning the
practicality of Pfair scheduling.
In this paper, we investigate this issue by comparing the PD2 Pfair
algorithm to the EDF-FF partitioning scheme, which uses first fit (FF) as
a partitioning heuristic and the earliest-deadline-first (EDF) algorithm
for per-processor scheduling. We present experimental results that show
that PD2 is competitive with, and in some cases outperforms, EDF-FF.
These results suggest that Pfair scheduling is a viable alternative to
partitioning. Furthermore, as discussed herein, Pfair scheduling
provides many additional benefits, such as simple and efficient
synchronization, temporal isolation, fault tolerance, and support for
- A. Srinivasan, P. Holman, J. Anderson, S.
Baruah, and J. Kaur.
Multiprocessor Scheduling in Processor-based
Router Platforms: Issues and Ideas,
Proceedings of the 2nd Workshop on Network Processors, pages
48-62, February 2003. Held in conjunction with the 9th
International Symposium on High-Performance Computer
Two important trends are expected to guide the design of
next-generation networks. First, with the commercialization of the
Internet, providers will use value-added services to differentiate their
service offerings from other providers; such services require the use
of sophisticated resource scheduling mechanisms in routers. Second, to
enable extensibility and the deployment of new services in a rapid and
cost-effective manner, routers will be instantiated using programmable
network processors. In this research, our goal is to develop
sophisticated multiprocessor scheduling mechanisms that would enable
networks that deploy such router platforms to provide service
guarantees to applications. Existing multiprocessor scheduling
techniques are either not applicable to router platforms due to their
complexity or simplistic assumptions, or are not based on rigorous
formalism, which is necessary to enable strong assertions about
service guarantees. In this work, we propose to address these
limitations. This paper presents our current ideas and planned future
- A. Srinivasan and S. Baruah.
Deadline-based Scheduling of Periodic Task Systems on Multiprocessors,
Information Processing Letters, Volume 84, Number 2, pages 93-98,
Elsevier Science Press, November 2002.
We consider the problem of scheduling periodic task systems on
multiprocessors and present a deadline-based scheduling
algorithm for solving this problem. We show that our algorithm
successfully schedules on m processors any periodic task system
with utilization at most m^2/(2m-1).
- A. Srinivasan, P. Holman, and J. Anderson.
Integrating Aperiodic and Recurrent Tasks on Fair-scheduled Multiprocessors,
Proceedings of the 14th Euromicro Conference on Real-Time
Systems, pages 19-28, June 2002.
We propose two server implementations for multiplexing aperiodic and
recurrent (i.e., periodic, sporadic, or rate-based) real-time tasks in
fair-scheduled multiprocessor systems. This is the first paper to
consider the problem of integrating support for aperiodic tasks within
fair multiprocessor scheduling algorithms. We also provide
admission-control tests for the scheduling of hard aperiodic tasks
(which have deadlines). Further, we point out some of the additional
complexities involved in server-based implementations on multiprocessors
and present some ways to handle them. Most of these complexities arise
because of the parallelism that exists in such systems. Finally, we
provide experimental results that demonstrate the effectiveness of our
- A. Srinivasan and J. Anderson.
Optimal Rate-based Scheduling on Multiprocessors, Proceedings of the
34th ACM Symposium on Theory of Computing, pages
189-198, May 2002.(A
of this paper is going to appear in Journal of Computer and System Sciences.)
The PD2 Pfair/ERfair scheduling algorithm is the most efficient known
algorithm for optimally scheduling periodic tasks on multiprocessors.
In this paper, we prove that PD2 is also optimal for scheduling
"rate-based" tasks whose processing steps may be highly jittered. The
rate-based task model we consider generalizes the widely-studied
sporadic task model.
- J. Anderson and A. Srinivasan.
Mixed Pfair/ERfair Scheduling of Asynchronous Periodic Tasks,
Proceedings of the 13th Euromicro Conference on Real-Time Systems,
pages 76-85, June 2001. (A
of this paper has appeared in Journal of Computer and
System Sciences, Volume 68, Number 1, pages 157-204, Elsevier Science
Press, February 2004.)
There has been much recent interest in multiprocessor Pfair and ERfair
scheduling algorithms. Under Pfair scheduling, each task is broken into
quantum-length subtasks, each of which must execute within a "window" of
time slots. These windows divide each period of a task into potentially
overlapping subintervals of approximately equal length. "Early-release"
fair (ERfair) scheduling was recently proposed as a work-conserving
variant of Pfair scheduling. Under ERfair scheduling, subtasks within
the same job are allowed to execute before their Pfair windows.
In this paper, we prove that a simplified variant of the PD Pfair
algorithm, called PD2, is optimal for scheduling any mix of
early-release and non-early-release asynchronous tasks on a
multiprocessor. This result breaks new ground in two ways. First, we are
the first to consider the problem of scheduling both early-release and
non-early-release tasks under a common framework. Second, all prior
work on optimal multiprocessor Pfair or ERfair scheduling algorithms has
been limited to synchronous periodic task systems.
- J. Anderson and A. Srinivasan.
Pfair Scheduling: Beyond Periodic Task Systems,
Proceedings of the 7th International Conference on Real-Time
Computing Systems and Applications, pages 297-306, December 2000.
version with full proofs.)
In this paper, we consider variants of Pfair and ERfair scheduling in
which subtasks may be released late, i.e., there may be separation
between consecutive windows of the same task. We call such tasks
intra-sporadic tasks. There are two main contributions of this paper.
First, we show the existence of a Pfair (and hence ERfair) schedule for
any intra-sporadic task system whose utilization is at most the number
of available processors. Second, we give a polynomial-time algorithm
that is optimal for scheduling intra-sporadic tasks in a Pfair or ERfair
manner on systems of one or two processors.
- J. Anderson and A. Srinivasan.
Early-Release Fair Scheduling,
Proceedings of the 12th Euromicro Conference on Real-Time Systems,
pages 35-43, June 2000.
We present a variant of Pfair scheduling, which we call early-release
fair (ERfair) scheduling. Like conventional Pfair scheduling, ERfair
scheduling algorithms can be applied to optimally schedule periodic
tasks on a multiprocessor system in polynomial time. However, ERfair
scheduling differs from Pfair scheduling in that it is work conserving. As
a result, average job response times may be much lower under ERfair
scheduling than under Pfair scheduling, particularly in lightly-loaded
systems. In addition, runtime costs are lower under ERfair scheduling.
This is because, in Pfair-scheduled systems, significant bookkeeping
information is required to determine when a job of a task is and is not
eligible for execution. In an ERfair system, this bookkeeping
information is not required because, once released, a job continues to
be eligible until it completes. To the best of our knowledge, ERfair
scheduling is the first truly work-conserving scheduling discipline for
periodic task systems that is optimal for multiprocessors.