1
$\begingroup$

In many papers about DAG (directed-acyclic graph) scheduling in distributed systems, the authors make the assumption that the communication between the processors of the system where the DAG is scheduled is contention-free.

Does that mean they assume that each communication link can transfer concurrently an infinite number of messages (connections) and each connection uses the full bandwidth of the communication link?

For example, in case there are 5 concurrent connections on a 100Mb/s communication link from processor A to processor B, the speed of each connection is assumed to be 100Mb/s instead of 20Mb/s (i.e. 100/5=20)?

Many thanks in advance.

$\endgroup$
1
$\begingroup$

Not my field of expertise, but I think this is a relaxation in comparison with real-life scenarios. In actual systems, once a connection has been established and a "packet" has been sent (what packet here means depends on the context of the problem being solved), it is possible that an unscheduled interrupt occurs that pauses this communication and allows a new communication with a different processor to occur.

I believe this relaxation means that once a "packet" is sent, we assume that the other processors do not interrupt this connection until this quantum of information has been sent. Essentially, it makes the processors being collaborators instead of antagonizers and it simplifies the analysis, while still keeping it reasonable, since all processors stick to the schedule and do not monopolize the connection (i.e. they will stop transmitting once this quantum of information has been sent, instead of maintaining their connection and sending their entire message in the expense of others, thus ignoring the schedule given).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.