NDLI: The Impact of Timing Knowledge on the Session Problem

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Rhee, Injong Welch, Jennifer L.
Copyright Year	2003
Abstract	The session problem is an abstraction of fundamental synchronization problems in distributed systems. It has previously been used as a test case to demonstrate the differences in the time needed to solve problems in several timing models. The goal of this paper is to compare the computational power of a family of partially synchronous models by studying the time needed to solve the session problem. Four timing parameters are considered: the maximum and minimum process step times and message delays. Timing models are obtained by considering independently whether each parameter is known (i.e., is hard-wired into the processes' code) or unknown, giving rise to four shared memory models and 16 message passing models. The models are compared based on the time complexity, measured in real time, of the session problem.This paper presents a modular proof technique for obtaining asymptotically tight bounds on the time complexity of the session problem for the four shared memory models and the 16 message passing models. Timing information known in each particular model can be exploited by algorithms to count sessions in different ways. This paper reports five different counting algorithms. The matching lower bound for each model suggests that they are the optimal ways to count sessions. Based on these bounds, a lattice among unknown parameter models is constructed, which confirms the common belief that as more timing information is known in a model, the model behaves more like a synchronous system.
Starting Page	1007
Ending Page	1039
Page Count	33
File Format	PDF
ISSN	00975397
DOI	10.1137/S009753979936094X
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	4
Volume Number	32
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2003-01-01
Access Restriction	Subscribed
Subject Keyword	Computational difficulty of problems partially synchronous models upper bounds timing information session problem Distributed algorithms distributed computing lower bounds
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

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

Upper and Lower Bounds on the Power of Advice

On Sparsification for Computing Treewidth

The aperiodic Domino problem in higher dimension

Partitioning Hypergraphs is Hard: Models, Inapproximability, and Applications

On optimal approximability results for computing the strong metric dimension

Lower bounds for the circuit size of partially homogeneous polynomials

Tensor Rank: Some Lower and Upper Bounds

On Computing a Center Persistence Diagram

Algorithms versus Circuit Lower Bounds

The Impact of Timing Knowledge on the Session Problem

Similar Documents

Upper and Lower Bounds on the Power of Advice

On Sparsification for Computing Treewidth

The aperiodic Domino problem in higher dimension

Partitioning Hypergraphs is Hard: Models, Inapproximability, and Applications

On optimal approximability results for computing the strong metric dimension

Lower bounds for the circuit size of partially homogeneous polynomials

Tensor Rank: Some Lower and Upper Bounds

On Computing a Center Persistence Diagram

Algorithms versus Circuit Lower Bounds

The Impact of Timing Knowledge on the Session Problem