Computationally Efficient Fault Tolerant ANTS
Article No.: 8, Pages 1 - 8
Abstract
In this paper, we formulate a method to utilize n mobile agents to solve a variant of Ants Nearby Treasure Search problem (ANTS), where an adversary can place treasure at any cell at a distance D from the origin. We devise a method which finds the treasure with the time complexity of O(D + D2 /n + Df) where D is the Manhattan distance of the treasure from the source and f is the maximum number of failures such that f ∈ o(n). The algorithm is specially designed to reduce computation complexity of the distributed system as a whole by efficiently handling failures and also, introducing the elements of parallelism with respect to handling failures. Using our algorithm, we bring down the computation cost/complexity of the system by an order of n, when failures occur, where n is the total number of ants. ANTS problem utilizes the multi-agent system with self-organization and steering based on a control mechanism which is analogous to the problem of discovering resources that are available to the distributed system.
References
[1]
I. Abraham and D. Dolev. Asynchronous resource discovery. Computer Networks, 50(10):1616--1629, 2006.
[2]
S. Albers and M. R. Henzinger. Exploring unknown environments. SIAM Journal on Computing, 29(4):1164--1188, 2000.
[3]
S. Davtyan, K. M. Konwar, and A. A. Shvartsman. Self-stabilizing resource discovery algorithm. In Principles of Distributed Systems, pages 129--144. Springer, 2013.
[4]
K. Diks, P. Fraigniaud, E. Kranakis, and A. Pelc. Tree exploration with little memory. In Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, pages 588--597. Society for Industrial and Applied Mathematics, 2002.
[5]
Y. Emek, T. Langner, D. Stolz, J. Uitto, and R. Wattenhofer. How many ants does it take to find the food? In Structural Information and Communication Complexity, pages 263--278. Springer, 2014.
[6]
Y. Emek, T. Langner, D. Stolz, J. Uitto, R. Wattenhofer, and I. Technion. Towards more realistic ants.
[7]
O. Feinerman and A. Korman. Memory lower bounds for randomized collaborative search and implications for biology. In Distributed Computing, pages 61--75. Springer, 2012.
[8]
O. Feinerman, A. Korman, Z. Lotker, and J.-S. Sereni. Collaborative search on the plane without communication. In Proceedings of the 2012 ACM symposium on Principles of distributed computing, pages 77--86. ACM, 2012.
[9]
M. Ghaffari, C. Musco, T. Radeva, and N. Lynch. Distributed house-hunting in ant colonies. arXiv preprint arXiv:1505.03799, 2015.
[10]
M. Harchol-Balter, T. Leighton, and D. Lewin. Resource discovery in distributed networks. In Proceedings of the eighteenth annual ACM symposium on Principles of distributed computing, pages 229--237. ACM, 1999.
[11]
T. Langner, J. Uitto, D. Stolz, and R. Wattenhofer. Fault-tolerant ants. In Distributed Computing, pages 31--45. Springer, 2014.
[12]
P. Panaite and A. Pelc. Exploring unknown undirected graphs. Journal of Algorithms, 33(2):281--295, 1999.
[13]
H. V. D. Parunak. "go to the ant": Engineering principles from natural multi-agent systems. Annals of Operations Research, 75:69--101, 1997.
[14]
P. Sousa, N. F. Neves, and P. Verissimo. How resilient are distributed f fault/intrusion-tolerant systems? In Dependable Systems and Networks, 2005. DSN 2005. Proceedings. International Conference on, pages 98--107. IEEE, 2005.
[15]
H. Van Dyke Parunak and S. Brueckner. Entropy and self-organization in multi-agent systems. In Proceedings of the fifth international conference on Autonomous agents, pages 124--130. ACM, 2001.
Recommendations
Middleware-Based Failure Detection and Recovery Services for Fault-Tolerant E-services
DESE '09: Proceedings of the 2009 Second International Conference on Developments in eSystems EngineeringThe runtime detection of failure and recovery from failure is a major challenge facing e-business and e-commerce applications. Different types of failure are well understood through the failure model, but the detection and differentiation between these ...
Modeling fault-tolerant and reliable mobile agent execution in distributed systems
EC'05: Proceedings of the 6th WSEAS international conference on Evolutionary computingThe reliable execution of a mobile agent is a very important design issue in building a mobile agent system and many fault-tolerant schemes have been proposed so far. To further develop mobile agent technology, reliability mechanisms such as fault ...
A fault-tolerant optimization mechanism for spatiotemporal data analysis in flink
AbstractSpatiotemporal data analysis plays a vital role in big data processing, and it is also a research hotspot in location-aware and recommender systems. In these applications, graph modeling and distributed iterative computing are the basis and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2016
339 pages
ISBN:9781450340649
DOI:10.1145/2925995
Copyright © 2016 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 25 July 2016
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
KMO '16
KMO '16: The 11th International Knowledge Management in Organizations Conference
July 25 - 28, 2016
Hagen, Germany
Acceptance Rates
KMO '16 Paper Acceptance Rate 47 of 96 submissions, 49%;
Overall Acceptance Rate 47 of 96 submissions, 49%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 66Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in