Efficient and Flexible Agreement Protocols Based on Trustworthiness Relation of Peers in Unstructured Peer-to-Peer Overlay Networks

Nowadays information systems are being shifted to distributed architectures to obtain the benefits like scalability, autonomy, and faulty-tolerance. Since peerto-peer (P2P) systems are open world systems differently from other systems like cloud computing model, a huge number of computers and various types of computers with P2P application are interconnected in large-scale P2P overlay networks lying on the top of underlying physical computer networks like the Internet Protocol (IP) network. Except centralized or hybrid P2P systems, there is no centralized index server which controls the whole P2P system, and the peers which represent the individual computers in the P2P system, autonomously take actions and cooperate with each other to realize their purpose such as file sharing, building distributed storage, instant messaging, realizing distributed computation, contents delivery, cooperative work, and so forth. Because of the nature of the P2P systems, it is difficult for every peer to figure out what kinds of information are distributed to what peers, what kinds of peers exist in P2P overlay networks, and what kinds of relations among peers are. In addition, malicious peers and faulty peers like a crash-faulty peer can join and leave a P2P system without being authenticated and authorized. This rises a question on how each peer to trust a target peer in the P2P systems. Therefore efficient and reliable synchronization methods are required to be supported in order to achieve the cooperation among peers in the P2P systems. The P2P system is a disruptive technology for deploying applications that scale to millions of simultaneous participants. Because each user contributes computer and networking resources, it offers a low-barrier-of-entry platform with high scalability. Extensions to the basic model could offer different grades of service as well as address limitations of the basic model. These limitations are due to the decentralized character of the overlay and the unreliability of the peers. As disruptive technology, P2P systems raise important questions about the long-term impact on other approaches for video delivery, telephony, and other information delivery services. In addition, P2P applications to date have been primarily adopted in the consumer space. Requirements for further growth such as manageability, security, or ability to generate revenue may in the near term require hybrid variations of the basic model. The ability to incorporate reliable and secure transactions is still nascent. An agreement or consensus procedure is one of the most essential parts in our daily life. In our history, many astonishing achievements are done by the collaboration of many peoples, like the pyramids in Egypt. In order to achieve the collaboration, we need agreement procedures for a group of multiple participants to support it, and that is why it is essential in our daily life. Without exception in computer world, we can find many footprints of agreement procedures in basic and important parts of the information systems. For example, the two-phase commit protocol (2PC) in transaction processing, distributed database systems, and computer networks. The two-phase commit protocol (2PC) is a typical type of an atomic commitment protocol. It is a distributed algorithm that coordinates all the processes that participate in a distributed atomic transaction on whether to commit or abort (roll back) the transaction. The 2PC protocol is a specialized type of consensus protocol. Following the transformation of the information systems from the traditional centralized client-server models to the decentralized distributed models like P2P systems, how to achieve the agreement procedure in fully distributed environment become a question to us to be solve. In human societies, participants make an agreement in more flexible and efficient ways. For example, participants can change their mind in the agreement procedure. In this dissertation, we first introduce the novel relations among values which each peer can take from a given domain, existentially (E-) and preferentially (P-) precedent relations, which describe the relations between values in the domain of a peer. If a peer can take a value b after taking a value a, the value a E-precedents the value b. Suppose a peer can take a pair of values a and b after taking value c, if the peer prefers the value a to the value b, it denotes the value a P-precedents the value b. Based on the precedent relations, we discuss the flexible agreement protocol. Then, in order to improve the efficiency of the agreement protocol, we newly introduced the concept of obtainable cuts, which is a set of values which are exchanged by the participants during the agreement procedure and also satisfies the agreement condition. In addition, by defining the forward and backward strategies and history of values which each peer has so far taken, we introduces an efficient way to discover the obtainable cuts in the history of peers, ultimately improves the overall performance of the agreement protocol. By introducing the multi-value exchange (MVE) scheme, the time spent for a complete agreement procedure can be significantly reduced, therefore the efficiency of agreement protocol is improved. In order to achieve the agreement procedure in a fully distributed system, many problems has to be solved, for example, how to exchange information among participants, how to detect the agreement condition being satisfied through out the network and so on. As one of the most important steps of the agreement procedure, the message exchange phase is in charge of delivering and collecting information from all participants in the group. To realized the distributed agreement procedures, reliable message exchange protocols among peers are required to be realized as the most important phase of the whole procedure. In order to achieve our goal which is required to efficiently and reliably realize agreement procedure in a fully distributed system, we newly proposed a trustworthiness-based broadcast (TBB) algorithms in addition to the multi-value exchange (MVE) scheme. In this dissertation, we show our approach to designing and realizing the agreement procedure in a fully distributed system. The evaluation results show that by using our proposed trustworthiness-based (TBB) scheme, totally 22 percentage of the unnecessary message broadcast can be reduced in the network compared with the multipoint relay algorithm and pure message flooding. Furthermore, a message can be delivered to every peer in presence of faulty peers. By improving the efficiency of the message exchange phase of the protocol, we improved the overall performance of the agreement protocol. The concepts, algorithms, implementation, and evaluation of the agreement protocol discussed in this dissertation can be not only theoretical but also practical foundation to design and develop various of applications on P2P overlay networks