Wyniki wyszukiwania - Biblioteka Nauki

1

How to Compute Times of Random Walks based Distributed Algorithms

100%

Bui A. , Sohier D.

|

tom Vol. 80, nr 4

363-378

EN

Random walk based distributed algorithms make use of a token that circulates in the system according to a random walk scheme to achieve their goal. To study their efficiency and compare it to one of the deterministic solutions, one is led to compute certain quantities, namely the hitting times and the cover time. Until now, only bounds on these quantities were known. First, this paper presents two generalizations of the notions of hitting and cover times to weighted graphs. Indeed, the properties of random walks on symmetrically weighted graphs provide interesting results on random walk based distributed algorithms, such as local load balancing. Both of these generalizations are proposed to precisely represent the behaviour of these algorithms, and to take into account what the weights represent. Then, we propose an algorithm to compute the n2 hitting times on a weighted graph of n vertices, which we improve to obtain a O(n3) complexity. This complexity is the lowest up to now. This algorithm computes both of the generalizations that we propose for the hitting times on a weighted graph. Finally, we provide the first algorithm to compute the cover time (in both senses) of a graph. We improve it to achieve a complexity of O(n32n). The algorithms that we present are all robust to a topological change in a limited number of edges. This property allows us to use them on dynamic graphs.

2

Integrating Distributed Algorithms into distributed systems

51%

Kindler E. , Peuker S.

|

1999

|

tom Vol. 37, Nr 3

291-309

EN

A distributed algorithm is often used as a part of a larger distributed system. Usually, the properties of an algorithm are proven for the algorithm in isolation. Then, it is not obvious how the algorithm behaves when integrated into a larger system. In this paper, we present a simple technique which allows to derive properties of an algorithm which is integrated into a distributed system from the properties of the algorithm in isolation. The technique exploits the fact that some actions of a distributed algorithm do not belong to the algorithm but are triggered by the environment. If these actions are distinguished and are adequately considered in the verification of the algorithm, basically all properties are still valid for the algorithm as a part of a larger distributed system. This result will be formalized in the setting of the Distributed Algorithms' Working Notation (DAWN). Based on this result, we will give a proof rule which allows to prove liveness properties of a system from liveness properties of the involved distributed algorithm.

3

ILF and DAWN for verifying distributed algorithms : an idea for a tool

51%

Baar T. , Kindler E.

|

1999

|

tom Vol. 37, Nr 3

201-211

EN

The Distributed Algorithms Working Notation (DAWN) was designed for modeling and veri-fying algorithms in an intuitive way. Nevertheless, DAWN proofs are formal. In this paper, we show that it is possible to check correctness of a DAWN proof fully auto-matically. For each step in a DAWN proof, we can generate a set proof obligations which can automatically be checked by help of automated theorem provers. The verification tool ILF provides a uniform interface to many theorem provers - which makes it an ideal partner for DAWN and a basis for building a DAWN-tool.

4

Leader election in rings with nonunique labels

51%

Dobrev S. , Pelc A.

|

2004

|

tom Vol. 59, nr 4

333--347

EN

We consider the leader election problem in a ring whose nodes have possibly nonunique labels. Every node knows a priori its own label and two integers, m and M, which are, respectively, a lower and an upper bound on the (unknown) size n of the ring. The aim is to decide whether leader election is possible and to perform it, if so. We consider both the synchronous and the asynchronous version of the problem and we are interested in message complexity in both cases. For the synchronous version we present an algorithm using O(n logn) messages and working in time O(M). Moreover, our algorithm uses O(n) messages when all identifiers are distinct. For the asynchronous version we show an Ω(nM) lower bound on message complexity for this problem, and present an algorithm for it using O(nM) messages.

5

An Efficient Message Passing Election Algorithm based on Mazurkiewicz's Algorithm

38%

Chalopin J. , Métivier Y.

|

2007

|

tom Vol. 80, nr 1-3

221-246

EN

We study the election and the naming problems in the asynchronous message passing model. We present a necessary condition based on Angluin's lifting lemma [1] that must be satisfied by any network that admits a naming (or an election) algorithm. We then show that this necessary condition is also sufficient: we present an election and naming algorithm based on Mazurkiewicz's algorithm [17]. The algorithm we obtained is totally asynchronous and it needs a polynomial number of messages of polynomial size, whereas previous election algorithms in this model are pseudo-synchronous and use messages of exponential size.

6

Selected application of the Chinese remainder theorem in multiparty computation

38%

Jakubski A.

Journal of Applied Mathematics and Computational Mechanics

|

2016

|

tom Vol. 15, nr 1

39-47

EN

In this paper we present protocols checking the equality of two distributed numbers and calculation of the product in such a way that the distributed numbers are unknown to anyone. The presented protocols use the Chinese Remainder Theorem. As a result, the obtained protocols have many interesting cryptographic features.

7

A Hybrid Protocol to Solve Authenticated Byzantine Consensus

32%

Tioura A. , Moumen H. , Kalla H. , Ait Saidi A.

Fundamenta Informaticae

|

2020

|

tom Vol. 173, nr 1

73--89

EN

The consensus is a central problem of fault-tolerant distributed computing. Unfortunately, solving such a problem is impossible in asynchronous distributed systems prone to process failures. To circumvent this impossibility (known as FLP impossibility result) in a deterministic way, on top of asynchronous distributed systems enriched with additional assumptions, several protocols have been proposed. Actually, to solve the Byzantine Consensus problem, with a deterministic manner, in systems where at most t processes may exhibit a Byzantine behavior, two approaches have been investigated. The first relies on the addition of synchrony, called Timer-Based, while the second, called Time-Free, is based on the pattern of message exchange. This paper shows that both types of assumptions are not antagonist and can be combined to solve authenticated Byzantine consensus. The combined assumption considers a correct process pi, called ⋄〈t + 1〉-BW, and a set X of t+1 correct processes (including pi itself) such that, eventually, for each query broadcasted by a correct process pj of X, pj receives a response from pi ∈ X among the (n – t) first responses to that query or both links connecting pi and pj are timely. Based on this combination, a simple hybrid authenticated Byzantine consensus protocol benefiting from the best of both worlds is proposed. As a matter of fact, although numerous hybrid protocols have been designed for the consensus problem in the crash model, this is, to our knowledge, the first hybrid deterministic solution to the Byzantine consensus problem.