NDLI: On Developing New Models, with Paging as a Case Study

Please wait, while we are loading the content...

Volume 40, Issue 4, December 2009

The book review column

SIGACT news complexity theory column 65

Introduction to the SIGACT news online algorithms column

Quantum computation and quantum communication: theory and experiments Author of book: Mladen Pavicic

On Developing New Models, with Paging as a Case Study

Quantum computing for computer scientists Noson S. Yanofsky and Mirco A. Mannucci, Cambridge University Press, 2008

Database theory column

Review of 5 of biologically inspired algorithms for financial modelling by Anthony Brabazon, Michael O'Neill Springer-Verlag Berlin Heidelberg, 2006

Distributed computing column 36 distributed computing

Review 17 of theoretical and experimental DNA computation by M. Amos Published in 2005 by Springer-Verlag Berlin Heidelberg

Barbara Liskov's turing award

Review 17 of theoretical and experimental DNA computation by M. Amos Published in 2005 by Springer-Verlag Berlin Heidelberg

A review of PODC 2009

Review of 18 coding for data and computer communications by David Salomon Springer, 2005

A review of DISC 2009

Technical report column

What theory for transactional memory?

Reliability and security in wireless networks

Theoretical aspects of dynamic distributed systems

Game-theoretic aspects of distributed computing

Review of SIROCCO 2009

Volume 40, Issue 3, Setember 2009

Volume 40, Issue 2, June 2009

Volume 40, Issue 1, March 2009

Issue 14, January 1972

Issue 13, December 1971

Issue 12, October 1971

Issue 11, August 1971

Issue 10, July 1971

Issue 9, April 1971

Issue 8, January 1971

Issue 7, September 1970

Issue 6, June 1970

Issue 4, January 1970

Issue 3, October 1969

Issue 2, July 1969

Issue 1, April 1969

On Developing New Models, with Paging as a Case Study

Content Provider	ACM Digital Library
Author	Dorrigiv, Reza López-Ortiz, Alejandro
Abstract	As computer science has progressed, numerous models and measures have been developed over the years. Among the most commonly used in theoretical computer science are the RAM model, the I/O model, worst case analysis, space (memory) usage, average case analysis, amortized analysis, adaptive analysis and the competitive ratio. New models are added to this list every few years to re ect varying constraints imposed by novel application or advances in computer architectures. Examples of alternative models are the transdichotomous RAM or word-RAM, the data stream model, the MapReduce model, the cache oblivious model and the smoothed analysis model. New models and measures, when successful expand our understanding of computation and open new avenues of inquiry. As it is to be expected relatively few models and paradigms are introduced every year, and even less are eventually proven successful. In this paper we discuss rst certain shortcomings of the online competitive analysis model particularly as it concerns paging, discuss existing solutions in the literature as well as present recent progress in developing models and measures that better re ect actual practice for the case of paging. From there we proceed to a more general discussion on how to measure and evaluate new models within theoretical computer science and how to contrast them, when appropriate, to existing models. Lastly, we highlight certain \natural" choices and assumptions of the standard worst-case model which are often unstated and rarely explicitly justied. We contrast these choices to those made in the formalization of probability theory.
Starting Page	98
Ending Page	123
Page Count	26
File Format	PDF
ISSN	01635700
DOI	10.1145/1711475.1714372
Journal	ACM SIGACT News (SIGA)
Volume Number	40
Issue Number	4
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1992-06-30
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in