NDLI: Coordinating time-constrained multi-agent resource sharing with fault detection

Content Provider	IEEE Xplore Digital Library
Author	Shieu-Hong Lin
Copyright Year	2011
Description	Author affiliation: Department of Mathematics and Computer Science, Biola University, USA (Shieu-Hong Lin)
Abstract	Sharing common resources in a distributed multi-agent environment requires coordination to avoid faulty system states. The statuses of resources such as personnel, equipments, and environmental factors at a point in time determine the system state at that time. When an agent takes an action at any time point within a scheduled time interval, it becomes a state-transition event occurring at that time. For each event, the underlying state transition relation can be compactly encoded as causal rules, which describe how statuses of resources and environmental factors may change in different ways based on preconditions before the event occurs. The central coordinator needs to check in advance whether any of the possible event sequences consistent with a proposed schedule may end in faulty system states. This fault detection task is NP-complete even for a polynomial-size state space in general. In this paper, we investigate the computational complexity of the fault detection task when agents fairly constrain the maximal length of time intervals. We develop a decomposition algorithm to divide the fault detection task over all events into subtasks involving subsets of the events with overlapping time intervals. For each subtask, only a subspace with reduced dimensionality is involved instead of the whole original state space. When the maximal length of time intervals is constrained below a fair threshold, we prove that with probability approaching one as the size of the problem instance grows the algorithm can accomplish the fault detection task in polynomial time even if the original underlying state space is exponential in size.
Starting Page	1000
Ending Page	1004
File Size	546683
Page Count	5
File Format	PDF
ISBN	9781457707407
ISSN	2157362X
e-ISBN	9781457707391
e-ISBN	9781457707384
DOI	10.1109/IEEM.2011.6118066
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2011-12-06
Publisher Place	Singapore
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Schedules Uncertainty Fault detection Clustering algorithms Polynomials Complexity theory Resource management
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