Search

Keeping strongly consistent the state of the replicas of a software service deployed across a distributed system prone to crashes and with highly unstable message transfer delays (e.g., the Internet), is a real practical challenge. The solution to this problem is subject to the FLP impossibility result, and thus there is a need for ‘long enough’ periods of synchrony with time bounds on process speeds and message transfer delays to ensure deterministic termination of any run of agreement protocols executed by replicas. This behavior can be abstracted by a partially synchronous computational model. In this setting, before reaching a period of synchrony, the underlying network can arbitrarily delay messages and these delays can be perceived as false failures by some timeout-based failure detection mechanism leading to unexpected service unavailability. This paper proposes a fully distributed solution for active software replication based on a three-tier software architecture well-suited to such a difficult setting. The formal correctness of the solution is proved by assuming the middle-tier runs in a partially synchronous distributed system. This architecture separates the ordering of the requests coming from clients, executed by the middle-tier, from their actual execution, done by replicas, i.e., the end-tier. In this way, clients can show up in any part of the distributed system and replica placement is simplified, since only the middle-tier has to be deployed on a well-behaving part of the distributed system that frequently respects synchrony bounds. This deployment permits a rapid timeout tuning reducing thus unexpected service unavailability. [ABSTRACT FROM AUTHOR]

Abstract: This paper studies the existence and the regularity of Logarithmic Harary Graphs (LHGs). This study is motivated by the fact that these graphs are employed for modeling the communication topology to support efficient flooding in the presence of link and node failures when considering an initial arbitrary number of nodes . Therefore, the capability to identify graph constraints that allow the construction of LHGs for the largest number of pairs (where is the desired degree of connectivity to be tolerant to failures) becomes of primary importance. The paper presents several results in that direction. We introduce a graph constraint, namely -PASTED-TREE, that allows the construction of a LHG for every pair such that . Secondly we present another graph constraint for LHG, namely -DIAMOND, which is equivalent to -PASTED-TREE in terms of capability to construct LHGs for any pair . The interest of -DIAMOND lies in the fact that, for a given , -DIAMOND allows us to construct more regular graphs than -PASTED-TREE does. A -regular graph shows the minimal number of links required by a -connected graph, leading to minimal flooding cost. The paper formally shows, in particular, that there are an infinite number of pairs , such that there exists a -regular LHG for the pair that satisfies -DIAMOND and does not satisfy -PASTED-TREE. [Copyright &y& Elsevier]