Name
Title | ||
|---|---|---|
Complexity of Minimum Length Scheduling for Precedence Constrained Messages in Distributed Systems |
Abstract | ||
|---|---|---|
Switching networks are the core of many communication and multiprocessor systems. In these systems, a set of entities (communication equipment or processors) communicate through the switching network by exchanging messages. Simultaneous transmission or reception of two or more different messages through an input or output port results in the corruption of the messages (also called collision), which are useless and must be retransmitted later. This causes a performance degradation. Collisions can be avoided only by a proper scheduling of the messages. The same problem also arises in single-hop purely optical WDM systems, where simultaneous reception or transmission over the same wavelength channel results in a collision. In this paper, we study the problem of minimum length scheduling of a set of messages subject to precedence constraints. We show that the decision version of the problem is NP-complete even in very restricted cases. This means that the optimization problem cannot be solved in polynomial time, unless P=NP. Since the problem cannot be optimally solved by fast algorithms, we then investigate the existence of polynomial time approximation algorithms, by first proving that approximation algorithms cannot exist with performance ratio bounded by $4/3$ or smaller and successively presenting an $\epsilon$-approximation algorithm with $\epsilon |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1109/71.888647 | IEEE Trans. Parallel Distrib. Syst. |
Keywords | Field | DocType |
proper scheduling,communication equipment,minimum length scheduling,polynomial time approximation algorithm,precedence constrained messages,simultaneous reception,performance degradation,optimization problem,polynomial time,approximation algorithm,performance ratio,approximation algorithms,scheduling,computer networks,np completeness,distributed system,communication complexity,distributed processing,distributed systems,testing | Approximation algorithm,Computer science,Scheduling (computing),Communication complexity,Multiprocessing,Real-time computing,Time complexity,Asymptotically optimal algorithm,Optimization problem,Bounded function,Distributed computing | Journal |
Volume | Issue | ISSN |
11 | 10 | 1045-9219 |
Citations | PageRank | References |
7 | 0.75 | 18 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Piera Barcaccia | 1 | 10 | 1.14 |
| Maurizio A. Bonuccelli | 2 | 373 | 48.31 |
| Miriam di Ianni | 3 | 144 | 17.27 |