Distributed algorithms for scheduling on line and tree networks

DOI10.1145/2332432.2332503MaRDI QIDQ2933811zbMATH OpenOpenAlexFDO

Authors Venkatesan T. Chakaravarthy, Sambuddha Roy, Yogish Sabharwal

Publication date 5 December 2014

Published in Proceedings of the 2012 ACM symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1205.1924

zbMATH Keywords

approximation algorithmschedulingunsplittable flow problem

Mathematics Subject Classification ID

Linear programming (90C05) Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25) Flows in graphs (05C21) Distributed algorithms (68W15) Distributed systems (68M14)

Abstract: We have a set of processors (or agents) and a set of graph networks defined over some vertex set. Each processor can access a subset of the graph networks. Each processor has a demand specified as a pair of vertices $<u,v>$, along with a profit; the processor wishes to send data between $u$ and $v$. Towards that goal, the processor needs to select a graph network accessible to it and a path connecting $u$ and $v$ within the selected network. The processor requires exclusive access to the chosen path, in order to route the data. Thus, the processors are competing for routes/channels. A feasible solution selects a subset of demands and schedules each selected demand on a graph network accessible to the processor owning the demand; the solution also specifies the paths to use for this purpose. The requirement is that for any two demands scheduled on the same graph network, their chosen paths must be edge disjoint. The goal is to output a solution having the maximum aggregate profit. Prior work has addressed the above problem in a distibuted setting for the special case where all the graph networks are simply paths (i.e, line-networks). Distributed constant factor approximation algorithms are known for this case. The main contributions of this paper are twofold. First we design a distributed constant factor approximation algorithm for the more general case of tree-networks. The core component of our algorithm is a tree-decomposition technique, which may be of independent interest. Secondly, for the case of line-networks, we improve the known approximation guarantees by a factor of 5. Our algorithms can also handle the capacitated scenario, wherein the demands and edges have bandwidth requirements and capacities, respectively.

Recommendations

• scientific article; zbMATH DE number 1929963
• Fast primal-dual distributed algorithms for scheduling and matching problems
• scientific article; zbMATH DE number 1305434
• Resource Allocation in Bounded Degree Trees
• Scheduling multicasts on unit-capacity trees and meshes.

Cited in

(6)

• Distributed Random Access Algorithm: Scheduling and Congestion Control
• Efficient allocation of chain-like task on chain-like network computers
• Improved algorithms for resource allocation under varying capacity
• DVS scheduling in a line or a star network of processors
• scientific article; zbMATH DE number 1929963 (Why is no real title available?)
• scientific article; zbMATH DE number 5629900 (Why is no real title available?)

This page was built for publication: Distributed algorithms for scheduling on line and tree networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2933811)