Global Convergence in Asynchronous Distributed Systems

Wireless sensor networks(WSNs) are often deployed to monitor physical and environmental conditions. Applications include forest fire detection, target tracking, disease prevention, etc. A major concern in WSNs is the overall reliability in the presence of faulty sensors or nodes. Achieving reliability in such systems often requires agreement among nodes to accomplish a common goal. This study is concerned with the agreement problem where the nodes need to collectively agree on a common value, even though each node may carry a different value and the system may contain some faulty nodes. The common value is approximate and may not be exactly the same among nodes. The process of reaching a common value is called Global Convergence (GC), in which the nodes experience a repeated pattern of collecting values from their neighbors, applying a convergent voting algorithm, and broadcasting the voted values to the neighbors. Each repeated pattern is called a round, which assist in decreasing disagreement among nodes until the convergence is reached. This study is conducted under the assumptions of partially connected systems where each node is able to communicate only with its immediate neighbors, hybrid faults where nodes with various severity of behavior, and asynchronous communication systems where each node performs algorithm at their clock. This research aims at the following goals for asynchronous GC in wireless distributed networks: the relationships among network size, node link density, and network diameter; the effect of different voting algorithms on GC speed; and the effect of less restricted link density on GC