NDLI: On detecting global predicates in distributed computations

Content Provider	IEEE Xplore Digital Library
Author	Mittal, N. Garg, V.K.
Copyright Year	2001
Description	Author affiliation: Dept. of Comput. Sci., Texas Univ., Austin, TX, USA (Mittal, N.)
Abstract	Monitoring of global predicates is a fundamental problem in asynchronous distributed systems. This problem arises in various contexts, such as design, testing and debugging, and fault tolerance of distributed programs. In this paper, we establish that the problem of determining whether there exists a consistent cut of a computation that satisfies a predicate in k-CNF (k/spl ges/2), in which no two clauses contain variables from the same process, is NP-complete in general. A polynomial-time algorithm to find the consistent cut, if it exists, that satisfies the predicate for special cases is provided. We also give algorithms (albeit exponential) that can be used to achieve an exponential reduction in time over existing techniques for solving the general version. Furthermore, we present an algorithm to determine whether there exists a consistent cut of a computation for which the sum x/sub 1/+x/sub 2/+/spl middot//spl middot//spl middot/+x/sub n/ exactly equals some constant k, where each x/sub i/ is an integer variable on a process p/sub i/ such that it is incremented or decremented by at most one at each step. As a corollary, any symmetric global predicate on Boolean variables, such as absence of simple majority and exclusive-OR of local predicates, can now be detected. Additionally, the problem is proved to be NP-complete if each x/sub i/ can be changed by an arbitrary amount at each step. Our results solve the previously open problems in predicate detection proposed by V.K. Garg (1997) and bridge the wide gap between the known tractability and intractability results that have existed until now.
Sponsorship	IEEE Comput. Soc. Tech. Committee on Distributed Process
Starting Page	3
Ending Page	10
File Size	782088
Page Count	8
File Format	PDF
ISBN	0769510779
DOI	10.1109/ICDSC.2001.918927
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2001-04-16
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Distributed computing Testing Debugging Computerized monitoring Fault tolerance Polynomials Bridges Fault detection Fault tolerant systems System recovery
Content Type	Text
Resource Type	Article

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