GLOBAL CONVERGENCE IN PARTIALLY FULLY CONNECTED NETWORKS (PFCN) WITH LIMITED RELAYS

Azad Azadmanesh (), Axel W. Krings and Bahador Ghahramani
Additional contact information
Azad Azadmanesh: University of Nebraska at Omaha, Department of Computer Science, Omaha, Ne 68182-0500, USA
Axel W. Krings: University of Idaho, Deptartment of Computer Science, Moscow, Idaho 83844-1010, USA
Bahador Ghahramani: University of Nebraska at Omaha, Department of Information Systems, Omaha, Ne 68182-0392, USA

International Journal of Information Technology & Decision Making (IJITDM), 2003, vol. 02, issue 02, 265-285

Abstract: In a distributed system, it is often necessary for nodes to agree on a particular event or to coordinate their activities. Applications of distributed agreement are many, such as Commit Protocols in distributed database systems, selection of a monitor node in a distributed system, detecting an intruder, or agreeing on the malicious behavior of a node.Among many forms of Distributed Agreement, one form is called Approximate Agreement (AA), in which the nodes, by exchanging their local values with other nodes, need to agree on values which are approximately equal to each other. Research on AA for fully connected networks is relatively mature. In contrast, the study of AA in partially connected networks has been very limited. More specifically, no general solution to the AA problem exists for such networks. This research solves the AA problem for a specific, scalable, partially connected network with limited relays. The research considers the worst failure mode of nodes, called Byzantine, and hybrid failure modes. The results show low communication cost in comparison to fully connected networks. The network is designed to take advantage of the results available for fully connected networks. Thus, the analysis for obtaining the expressions for Convergence Rate and Fault Tolerance becomes relatively easy.

Keywords: Approximate agreement; Byzantine agreement; clock synchronization; convergent voting algorithms; fault-tolerant multiprocessors; mixed-mode faults; sensor networks (search for similar items in EconPapers)
Date: 2003
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S021962200300063X
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijitdm:v:02:y:2003:i:02:n:s021962200300063x

Ordering information: This journal article can be ordered from

DOI: 10.1142/S021962200300063X

Access Statistics for this article

International Journal of Information Technology & Decision Making (IJITDM) is currently edited by Yong Shi

More articles in International Journal of Information Technology & Decision Making (IJITDM) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().