博碩士論文查詢聯邦系統首頁 聯絡信箱 關於我們 加入我們

本論文已被瀏覽 35 次, [ 造訪詳細資料與全文 ] 35 次,[ 回到前頁查詢結果 ] [ 重新搜尋 ]

Distributed House-Hunting in Ant Colonies.

作者:Mohsen Ghaffari, Cameron Nicholas Musco, Tsvetomira T. Radeva, Nancy Ann Lynch,
出版單位:Association for Computing Machinery (ACM)
核准日期:2016-01-15
類型:Article http //purl.org/eprint/type/ConferencePape
權限:Creative Commons Attribution-Noncommercial-Share Alike.http://creativecommons.org/licenses/by-nc-sa/4.0/....

英文摘要

We introduce the study of the ant colony house-hunting problem from a distributed computing perspective. When an ant colony's nest becomes unsuitable due to size constraints or damage, the colony relocates to a new nest. The task of identifying and evaluating the quality of potential new nests is distributed among all ants. They must additionally reach consensus on a final nest choice and transport the full colony to this single new nest. Our goal is to use tools and techniques from distributed computing theory in order to gain insight into the house-hunting process. We develop a formal model for the house-hunting problem inspired by the behavior of the Temnothorax genus of ants. We then show a Omega(log n) lower bound on the time for all n ants to agree on one of k candidate nests. We also present two algorithms that solve the house-hunting problem in our model. The first algorithm solves the problem in optimal O(log n) time but exhibits some features not characteristic of natural ant behavior. The second algorithm runs in O(k log n) time and uses an extremely simple and natural rule for each ant to decide on the new nest.

United States. Air Force Office of Scientific Research (Contract FA9550-13-1-0042)

National Science Foundation (U.S.) (Award 0939370-CCF)

National Science Foundation (U.S.) (Award CCF-AF-0937274)


無相關資訊


無相關資訊

 

計畫贊助者: