XPost: columbia.general.bboard, cs.bboard 
 From: galil@news.cs.columbia.edu 
  
 Title:         How Fair is Your Queue=20 
 =20 
 Speaker:    Hanoch Levy*, School of Computer Science, Tel-Aviv = 
 University, Tel-Aviv, Israel =20 
  
 When:     Wed Feb 11, 2004 @ 2 pm 
  
 Where:    Interschool Lab 
                Seventh Floor, CEPSR building 
                Columbia University 
  
 Host:        Prof. E Coffman 
  
 Abstract: 
  
  
 How should customers be served in a queue in order to grant them fair = 
 service? Most ordinary persons may consider the First-in-First-Out = 
 (FIFO) as the most fair policy and Last-in-First-Out (LIFO) as the most = 
 unfair policy. In contrast, some recent queueing studies suggest exactly = 
 the opposite, namely that LIFO (preemptive) is "always fair" and FIFO is = 
 "always unfair". Such queueing scheduling issues and many others show up = 
 in a large variety of applications in computer systems, Web servers and = 
 public or private facilities.=20 
  
 Recent studies show that fairness in queues is very important to humans, = 
 perhaps not less than the waiting itself. Further, many common queue = 
 disciplines (e.g. a special queue for short jobs in a supermarket) are = 
 being justified under the "cause of fairness". In fact, perhaps the most = 
 important cause for using a queue at all, is "fairness" among the queue = 
 users.=20 
  
 Nonetheless, Queueing Theory that has been developed for several = 
 decades, has hardly dealt with this issue, and an agreed upon measure of = 
 queueing fairness does not exist. The objective of this work is to = 
 understand queue fairness and develop a fairness measure that can be = 
 used by theorists and practitioners to evaluate the fairness level (and = 
 thus quality) of their system.=20 
  
 We propose a Resource Allocation Queueing Fairness Measure (RAQFM) which = 
 is unique in accounting for the intricate relations between jobs within = 
 the queue. RAQFM is sensitive to both seniority and service = 
 requirements. RAQFM also yields itself to analysis via common = 
 queueing-theory machinery. Lastly, RAQFM can bridge the major conceptual = 
 gap presented above, between the beliefs of ordinary people (FIFO more = 
 fair than LIFO) and recent queueing theory results (LIFO more fair than = 
 FIFO). We analyze RAQFM and demonstrate its properties.=20 
  
 * Joint work with Benjamin Avi-Itzhak and David Raz.=20 
  
 --- SoupGate-Win32 v1.05 
  * Origin: you cannot sedate... all the things you hate (1:229/2)