Lazy scheduling of processing and transmission tasks in collaborative systems

ABSTRACT

A collaborative system must perform both processing and transmission tasks. We present a policy for scheduling these tasks on a single core that is inspired by studies of human perception and the real-time systems field. It lazily delays the execution of the processing task if the delay cannot be noticed by humans. We use simulations and formal analysis to compare this policy with previous scheduling policies. We show that the policy trades-off an unnoticeable degradation in performance of some users for a much larger noticeable improvement in performance of others.

REFERENCES

• 1: Abdelkhalek, A., Bilas, A., and Moshovos, A. 2001. Behavior and performance of interactive multi-player game servers. ISPASS 2001.
• 2: Brosh, E. and Shavitt, Y. 2004. Approximation and heuristic algorithms for minimum delay application-layer multicast trees. INFOCOM 2004.
• 3: Saul Greenberg , David Marwood, Real time groupware as a distributed system: concurrency control and its effect on the interface, Proceedings of the 1994 ACM conference on Computer supported cooperative work, p.207-217, October 22-26, 1994, Chapel Hill, North Carolina, United States [doi>10.1145/192844.193011]
• 4: Caroline Jay , Mashhuda Glencross , Roger Hubbold, Modeling the effects of delayed haptic and visual feedback in a collaborative virtual environment, ACM Transactions on Computer-Human Interaction (TOCHI), v.14 n.2, p.8-es, August 2007 [doi>10.1145/1275511.1275514]
• 5: Junuzovic, S. and Dewan, P. 2008. Serial vs. concurrent scheduling of transmission and processing tasks in collaborative systems. CollaborateCom 2008.
• 6: Du Li , Rui Li, An Operational Transformation Algorithm and Performance Evaluation, Computer Supported Cooperative Work, v.17 n.5-6, p.469-508, December 2008 [doi>10.1007/s10606-005-9008-6]
• 7: p2pSim: a simulator for peer-to-peer protocols. http://pdos.csail.mit.edu/p2psim/kingdata. Mar 4, 2009.
• 8: Balasubramanian Seshasayee , Ripal Nathuji , Karsten Schwan, Energy-Aware Mobile Service Overlays: Cooperative Dynamic Power Management in Distributed Mobile Systems, Proceedings of the Fourth International Conference on Autonomic Computing, p.6, June 11-15, 2007 [doi>10.1109/ICAC.2007.14]
• 9: Shneiderman, B. 1998. Response time and display rate. in Designing the user-interface: strategies for effective human-computer interaction. Addison-Wesley Longman.
• 10: Sun, J. and Liu, J. 1996. Synchronization protocols in distributed real-time systems. ICDCS 1996.
• 11: Youmans, D.M. 1981. User requirements for future office workstations with emphasis on preferred response times. IBM United Kingdom Laboratories.
• 12: Bo Zhang , T. S. Eugene Ng , Animesh Nandi , Rudolf Riedi , Peter Druschel , Guohui Wang, Measurement based analysis, modeling, and synthesis of the internet delay space, Proceedings of the 6th ACM SIGCOMM conference on Internet measurement, October 25-27, 2006, Rio de Janeriro, Brazil [doi>10.1145/1177080.1177091]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Client/server

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
analytical model, collaboration architecture, local and remote response times, scheduling policy, simulations