Show simple item record

dc.contributor.authorHarchol-Balter, Moren_US
dc.contributor.authorCrovella, Mark E.en_US
dc.contributor.authorMurta, Cristina D.en_US
dc.date.accessioned2011-10-20T04:37:47Z
dc.date.available2011-10-20T04:37:47Z
dc.date.issued1997-10-31
dc.identifier.citationHarchol-Balter, Mor; Crovella, Mark; Murta, Cristina. "To queue or not to queue?: When FCFS is better than PS in a distributed system", Technical Report BUCS-1997-017, Computer Science Department, Boston University, October 31, 1997. [Available from: http://hdl.handle.net/2144/1617]
dc.identifier.urihttps://hdl.handle.net/2144/1617
dc.description.abstractWe examine the question of whether to employ the first-come-first-served (FCFS) discipline or the processor-sharing (PS) discipline at the hosts in a distributed server system. We are interested in the case in which service times are drawn from a heavy-tailed distribution, and so have very high variability. Traditional wisdom when task sizes are highly variable would prefer the PS discipline, because it allows small tasks to avoid being delayed behind large tasks in a queue. However, we show that system performance can actually be significantly better under FCFS queueing, if each task is assigned to a host based on the task's size. By task assignment, we mean an algorithm that inspects incoming tasks and assigns them to hosts for service. The particular task assignment policy we propose is called SITA-E: Size Interval Task Assignment with Equal Load. Surprisingly, under SITA-E, FCFS queueing typically outperforms the PS discipline by a factor of about two, as measured by mean waiting time and mean slowdown (waiting time of task divided by its service time). We compare the FCFS/SITA-E policy to the processor-sharing case analytically; in addition we compare it to a number of other policies in simulation. We show that the benefits of SITA-E are present even in small-scale distributed systems (four or more hosts). Furthermore, SITA-E is a static policy that does not incorporate feedback knowledge of the state of the hosts, which allows for a simple and scalable implementation.en_US
dc.description.sponsorshipNational Science Foundation (Postdoctoral Fellowship in the Mathematical Sciences, CCR-9501822, CCR-9706685); CAPES-Brazilen_US
dc.language.isoen_US
dc.publisherBoston University Computer Science Departmenten_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-1997-017
dc.titleTo Queue or Not to Queue: When Queueing is Better Than Timesharing in a Distributed Systemen_US
dc.typeTechnical Reporten_US


This item appears in the following Collection(s)

Show simple item record