Distributed algorithms for scheduling on line and tree networks

DOI10.1145/2332432.2332503zbMATH Open1301.68266arXiv1205.1924OpenAlexW1973053408MaRDI QIDQ2933811FDOQ2933811

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)

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.

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)

Cited In (6)

• Efficient allocation of chain-like task on chain-like network computers
• DVS scheduling in a line or a star network of processors
• Title not available (Why is that?)
• Improved algorithms for resource allocation under varying capacity
• Distributed Random Access Algorithm: Scheduling and Congestion Control
• Title not available (Why is that?)

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)