Many practical computing problems concern large graphs. Standard examples include the Web graph and various social networks. The scale of these graphs - in some cases billions of vertices, trillions of edges - poses challenges to their efficient processing. In this paper we present a computational model suitable for this task. Programs are expressed as a sequence of iterations, in each of which a vertex can receive messages sent in the previous iteration, send messages to other vertices, and modify its own state and that of its outgoing edges or mutate graph topology. This vertex-centric approach is flexible enough to express a broad set of algorithms. The model has been designed for efficient, scalable and fault-tolerant implementation on clusters of thousands of commodity computers, and its implied synchronicity makes reasoning about programs easier. Distribution-related details are hidden behind an abstract API. The result is a framework for processing large graphs that is expressive and easy to program.

No abstract available.

No abstract available.

Earlier work has developed the rudiments of a scheduling theory for computations having intertask dependencies - modeled via dags - for Internet-based computing. The goal of the schedules produced is to render tasks eligible for execution as fast as possible, with the aim of: (a) utilizing clients' computational resources well, by always having work to allocate to an available client; (b) lessening the likelihood of a computation's stalling for lack of eligible tasks. Simulation studies suggest that this goal does accelerate computation over the Internet. The theory crafts a schedule for a dag Q by "parsing" Q (if possible) into connected building-block dags that one can "compose " to form Q and then analyzing the scheduling dependencies among these building blocks. The current paper extends the theory by developing the Sweep Algorithm, a tool that allows one to: (1) schedule using building blocks that are not necessarily connected, and (2) craft schedules that interleave the execution of subdags that have no interdependencies. The augmented scheduling algorithms allow one to craft optimal schedules for previously unschedulable dags. Examples presented include artificial dags that are "close" to ones arising in real computations, as well as a component of a dag that arises in a functional MRI application.

Earlier work has developed the underpinnings of IC-scheduling theory, an algorithmic framework for scheduling computations having intertask dependencies for Internet-based computing (IC). The theory aims to produce schedules that render tasks eligible for execution at the maximum possible rate, so as to: (a) utilize remote clients' computational resources well, by always having work available for allocation; (b) lessen the likelihood that a computation can stall for lack of tasks that are eligible for execution. The current paper reconnects the theory, which models computations abstractly, with a variety of significant real computations and computational paradigms, by illustrating how to schedule these computations optimally.

Earlier work has developed the underpinnings of the IC-scheduling theory, a framework for scheduling computations having intertask dependencies - modeled via directed acyclic graphs (DAGs) - for Internet-based computing. The goal of the schedules produced is to render tasks eligible for execution at the maximum possible rate, with the dual aim of 1) utilizing remote clients' computational resources well by always having work to allocate to an available client and 2) lessening the likelihood of a computation's stalling for lack of eligible tasks. The DAGs handled by the theory thus far are those that can be decomposed into a given collection of bipartite building block DAGs via the operation of DAG decomposition. A basic tool in constructing schedules is a relation >, which allows one to "prioritize" the scheduling of a complex DAG's building blocks. The current paper extends the IC-scheduling theory in two ways: by expanding significantly the repertoire of DAGs that the theory can schedule optimally and by allowing one sometimes to shortcut the algorithmic process required to find optimal schedules. The expanded repertoire now allows the theory to schedule optimally, among other DAGs, a large range of DAGs that are either "expansive", in the sense that they grow outward from their sources, or "reductive", in the sense that they grow inward toward their sinks. The algorithmic shortcuts allow one to "read off" an optimal schedule for a DAG from a given optimal schedule for the DAG's dual, which is obtained by reversing all arcs (thereby exchanging the roles of sources and sinks).

Our earlier paper introduced a parallel scheduling problem where a directed acyclic graph modeling t tasks and their dependencies needs to be executed on n unreliable workers. Worker i executes task j correctly with probability p i,j . The goal is to find a regimen Σ, that dictates how workers get assigned to tasks (possibly in parallel and redundantly) throughout execution, to minimize the expected completion time. The paper provided a polynomial time algorithm for the problem restricted to the case when dag width and the number of workers are at most a constant, and showed necessity of these restrictions, unless P=NP. The current paper describes algorithm engineering approaches used to produce an efficient implementation of the algorithm, and experiments demonstrating how the algorithm scales.

It is often difficult to perform efficiently a collection of jobs with complex job dependencies due to temporal unpredictability of the grid. One way to mitigate the unpredictability is to schedule job execution in a manner that constantly maximizes the number of jobs that can be sent to workers. A recently developed scheduling theory provides a basis to meet that optimization goal. Intuitively, when the number of such jobs is always large, high parallelism can be maintained, even if the number of workers changes over time in an unpredictable manner. In this paper we present the design, implementation, and evaluation of a practical scheduling tool inspired by the theory. Given a DAGMan input file with interdependent jobs, the tool prioritizes the jobs. The resulting schedule significantly outperforms currently used schedules under a wide range of system parameters, as shown by simulation studies. For example, a scientific data analysis application, AIRSN, was executed at least 13% faster with 95% confidence. An implementation of the tool was integrated with the Condor high-throughput computing system

Earlier work has developed the underpinnings of a theory of scheduling computations having intertask dependencies - modeled via dags - for Internet-based computing. The goal of the schedules produced is to render tasks eligible for execution at the maximum possible rate. This goal aims: (a) to utilize remote clients’ computational resources well, by always having work to allocate to an available client; (b) to lessen the likelihood of the "gridlock" that ensues when a computation stalls for lack of eligible tasks. The dags handled by the theory thus far are those that can be constructed from a given collection of bipartite building-block dags via the operation of dagcomposition. The current paper extends the range of applicability of the theory by significantly expanding the repertoire of building-block dags that the scheduling algorithms can handle. Thereby, the theory can now schedule large classes of "expansive" and "reductive" dags optimally.

Conceptual and algorithmic tools are developed as a foundation for a theory of scheduling complex computation-dags for Internet-based computing. The goal of the schedules produced is to render tasks eligible for allocation to remote clients (hence, for execution) at the maximum possible rate. This allows one to utilize remote clients well, as well as to lessen the likelihood of the "gridlock" that ensues when a computation stalls for lack of eligible tasks. Earlier work has introduced a formalism for studying this optimization problem and has identified optimal schedules for several significant families of structurally uniform dags. The current paper extends this work via a methodology for devising optimal schedules for a much broader class of complex dags, which are obtained via composition from a prespecified collection of simple building-block dags. The paper provides a suite of algorithms that decompose a given dag /spl Gscr/ to expose its building blocks and an execution-priority relation /spl utri/ on building blocks. When the building blocks are appropriately interrelated under /spl utri/ the algorithms specify an optimal schedule for /spl Gscr/.

This paper introduces a theory of avalanche-creating and error-controlling encoding schemes. We consider a Hamming space {0, 1}nand the problem of finding a bijection g : {0, 1}nrarr {0, 1}n, with inverse h = g-1, that creates avalanche and controls error. That is, for any vectors u and v that are at most b1apart, their images g(u) and g(v) are at least b2apart; and for any vectors v and e, the distance between h(g(v) + e) and v is at most the length of e (the distance from e to 0n) plus b3. It appears that the two objectives of achieving avalanche effect and error control simultaneously in a single encoding scheme are contradictory. This paper is the first attempt at understanding the tradeoffs. Toward this end, the paper determines nontrivial cases when desired encoding schemes can be efficiently constructed, cases when schemes exist but it is not known how to construct them efficiently, and cases when schemes do not exist at all

This paper introduces a parallel scheduling problem where a directed acyclic graph modeling t tasks and their dependencies needs to be executed on n unreliable workers. Worker i executes task j correctly with probability pi,j. The goal is to find a regimen Ε, that dictates how workers get assigned to tasks (possibly in parallel and redundantly) throughout execution, so as to minimize expected completion time. This fundamental parallel scheduling problem arises in grid computing and project management fields, and has several practical applications.We show a polynomial time algorithm for the problem restricted to the case when dag width is at most a constant and the number of workers is also at most a constant. These two restrictions may appear to be too severe. However, they are fundamentally required. Specifically, we demonstrate that the problem is NP-hard with constant number of workers when dag width can grow, and is also NP-hard with constant dag width when the number of workers can grow. When both dag width and the number of workers are unconstrained, then the problem is inapproximable within factor less than 5/4, unless P=NP.

Martel [C. Martel, A. Park, and R. Subramonian, SIAM J. Comput., 21 (1992), pp. 1070--1099] posed a question for developing a work-optimal deterministic asynchronous algorithm for the fundamental load-balancing and synchronization problem called Certified Write-All (CWA). In this problem, introduced in a slightly different form by Kanellakis and Shvartsman in a PODC'89 paper [P. C. Kanellakis and A. A. Shvartsman, Distributed Computing, 5 (1992), pp. 201--247], p processors must update n memory cells and only then signal the completion of the updates. It is known that solutions to this problem can be used to simulate synchronous parallel programs on asynchronous systems with worst-case guarantees for the overhead of a simulation. Such simulations are interesting because they may increase productivity in parallel computing since synchronous parallel programs are easier to reason about than are asynchronous ones. This paper presents the first solution to the question of Martel, Park, and Subramonian. Specifically, we show a deterministic asynchronous algorithm for the CWA problem. Our algorithm has the work complexity of O(n+p 4 log n). This work complexity is asymptotically optimal for a nontrivial number of processors $p \leq \left(n/\log n\right)^{1/4}$. In contrast, all known deterministic algorithms require superlinear in n work when p = n 1/r for any fixed $r \geq 1$. Our algorithm generalizes the collision principle introduced by Buss et al. [J. Buss, P. C. Kanellakis, P. L. Ragde, and A. A. Shvartsman, J. Algorithms, 20 (1996), pp. 45--86] in 1996, which has not been previously generalized despite various attempts. Each processor maintains a collection of intervals of {1,2,...,n}. Any processor iteratively selects an interval and works from its tip toward the other tip until it finishes the work or collides with another processor. Collisions are detected effectively using a special Read-Modify-Write operation. In any case, the processor transforms its collection appropriately. Our analysis shows that the transformations preserve some structural properties of collections of intervals. This guarantees that work is assigned to processors in an efficient manner.

In their SIAM J. on Computing paper [33] from 1992, Martel et al. posed a question for developing a work-optimal deterministic asynchronous algorithm for the fundamental loadbalancing and synchronization problem called Certified Write-All. In this problem, introduced in a slightly different form by Kanellakis and Shvartsman in a PODC’89 paper [20], p processors must update n memory cells and only then signal the completion of the updates. It is known that solutions to this problem can be used to simulate synchronous parallel programs on asynchronous systems with worst-case guarantees for the overhead of a simulation. Such simulations are interesting because they may increase productivity in parallel computing since synchronous parallel programs are easier to reason about than asynchronous ones are. This paper presents the first solution to the question of Martel et al. Specifically, we show a deterministic asynchronous algorithm for the Certified Write-All problem. Our algorithm has the work complexity of O(n + p 4 log n). This work complexity is asymptotically optimal for a nontrivial number of processors p ≤ (n / log n) 1/4. In contrast, all known deterministic algorithms require superlinear in n work when p = n 1/r, for any fixed r ≥ 1.

A prevailing feature of mobile telephony systems is that the cell where a mobile user is located may be unknown. Therefore when the system is to establish a call between users it may need to search, or page, all the cells that it suspects the users are located in, to find the cells where the users currently reside. The search consumes expensive wireless links and so it is desirable to develop search techniques that page as few cells as possible.We consider cellular systems with c cells and m mobile users roaming among the cells. The location of the users is uncertain as given by probability distribution vectors. Whenever the system needs to find specific users, it conducts a search operation lasting some number of rounds (the delay constraint). In each round the system may check an arbitrary subset of cells to see which users are located there. In this setting the problem of finding one user with minimum expected number of cells searched is known to be solved optimally in polynomial time.In this paper we address the problem of finding several users with the same optimization goal. This task is motivated by the problem of establishing a conference call between mobile users. We first show that the problem is NP-hard. Then we prove that a natural and simple heuristic is a e/e-1 approximation solution.

The emergence of mobile computing paradigms has created new dimensions for the problem of performing a collection of tasks in a distributed setting. Indeed, an intrinsic feature of mobile computing is that the communication topology changes over time, and some devices may not be able to communicate with others for prolonged periods of time. Efficient utilization of resources in such a setting requires tools for structuring computation with highly variable, or absent, processor connectivity. This article provides a family of efficient distributed scheduling building blocks for this purpose. Specifically, this paper presents new bounds for a fundamental distributed cooperation problem under the assumption that processors may need to schedule their work in isolation due to a prolonged absence of communication. The problem for n processors is defined in terms of t tasks that must be performed efficiently and that are known to all processors. This study gives tight bounds on the ability of the processors to schedule their work so that when some group of processors establish communication, the wasted (redundant) work these processors have collectively performed prior to that time is controlled.

We consider a distributed environment consisting of n processors that need to perform t tasks. We assume that communication is initially unavailable and that processors begin work in isolation. At some unknown point of time an unknown collection of processors may establish communication. Before processors begin communication they execute tasks in the order given by their schedules. Our goal is to schedule work of isolated processors so that when communication is established for the first time, the number of redundantly executed tasks is controlled. We quantify worst case redundancy as a function of processor advancements through their schedules.

The problem of performing t tasks on n asynchronous or undependable processors is a basic problem in parallel and distributed computing. We consider an abstraction of this problem called the Write-All problem— using n processors write 1's into all locations of an array of size t. The most efficient known deterministic asynchronous algorithms for this problem are due to Anderson and Woll. The first class of algorithms has work complexity of Ο(t . n ε), for n ≰ ty and any ε > 0, and they are the best known for the full range of processors (n = t). To schedule the work of the processors, the algorithms use sets of q permutations on [q] (q ≰ n) that have certain combinatorial properties. Instantiating such an algorithm for a specific ε either requires substantial pre-processing (exponential in 1/ε2) to find the requisite permutations, or imposes a prohibitive constant (exponential in 1/ε3) hidden by the asymptotic analysis. The second class deals with the specific case of t = nu, u ≰ 2, and these algorithms have work complexity of Ο(t log t). They also use sets of permutations with the same combinatorial properties. However instantiating these algorithms requires exponential in n preprocessing to find the permutations. To alleviate this costly instantiation Kanellakis and Shvartsman proposed a simple way of computing the permutation schedules. They conjectured that their construction has the desired properties but they provided no analysis.

This work studies a distributed cooperation problem under an extreme assumption that no two processors may be able to communicate during a prolonged period of time. For problems where the quality of distributed decision-making depends on, and can be traded for, communication, the solution space needs to consider the possibility of no communication. Notably, this is the case in the load-balancing setting introduced by Papadimitriou and Yanakakis [PY] and studied by Georgiades, Mavronicolas and Spirakis [GMS]. The distributed cooperation problem that we consider here is defined for n processors in terms of t tasks that need to be performed efficiently and that are known to all processors. The fact that the tasks are initially known makes it possible for the problem to be solved in the absence of communication. The efficiency requirement and the possibility of eventual availability of communication make it desirable to structure the work of the processors so that when eventually some processors are able to communicate, the amount of wasted (redundant) work they have collectively performed prior to that time is controlled. We model solutions to the problem as sets of n lists of distinct tasks from {1,… ,t}. We call such lists schedules. We define and study the notion of k-waste that, for a set of n schedules, measures the maximum number of redundant task identifiers contained in any subset of k (≤ n) schedules. We are interested in expressing k-waste as a function of the length of schedules. Our goal is to construct n schedules of length t such that k-waste is controlled for any prefixes of the schedules.

This work presents a new renegotiated flexibly-priced communication service. The service is based on a novel auction-based flexible pricing scheme, where the flexibility is expressed in terms of client-supplied budget functions that represent the upper bound on the bandwidth unit price the client is willing to pay, as a function of time. This flexibility allows for the admission control and the bandwidth maintenance policies of the scheme to be decentralized. The policies are implemented by the involved switches in a distributed fashion, such that the clients do not need to participate so long as their budget functions remain competitive. We define four measures of flow satisfaction in terms of the quality and the price. We have performed a comprehensive simulation study of the scheme that confirms its positive qualities. One of the main observations is that clients benefit financially when choosing flexible budget functions, when compared to clients that use fixed budget functions and that achieve similar quality of service. Flexible flows achieving 90% throughput satisfaction can save from 7% to 12% in bandwidth unit price, and flows that may be content with lower satisfaction can save up to 46%.