PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 12

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  distributed algorithms
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote A Hybrid Protocol to Solve Authenticated Byzantine Consensus
Tioura Abdelhamid, Moumen Hamouma, Kalla Hamoudi, Ait Saidi Ahmed
Fundamenta Informaticae
|
2020
|
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.
2
Content available Selected application of the Chinese remainder theorem in multiparty computation
Jakubski A.
Journal of Applied Mathematics and Computational Mechanics
|
2016
|
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.
3
Content available remote Core for Large Datasets : Rough Sets on FPGA
Kopczyński M., Grześ T., Stepaniuk J.
Fundamenta Informaticae
|
2016
|
Vol. 147, nr 2/3
241--259
EN
This paper presents FPGA and softcore CPU based device for large datasets core calculation using rough set methods. Presented architectures have been tested on two real datasets by downloading and running presented solutions inside FPGA. Tested datasets had 1 000 to 10 000 000 objects. The same operations were performed in software implementation. Obtained results show the big acceleration in computation time using hardware supporting core generation in comparison to pure software implementation.
4
Analysis of an algorithm of distributed generation of matrices for markovan models of a congestion control mechanism
Bylina J., Bylina B.
Studia Informatica
|
2008
|
Vol. 29, nr 4B
93-102
EN
We consider the parallel generation of matrices corresponding to models of congestion control mechanisms' behavior. We develop a piece of software for a cluster architecture and analyze its performance times, amount of communication, each processor's load. The resulting application is scalable and also produces a substantial speedup and efficiency.
PL
Rozważamy równoległą generację macierzy odpowiadających modelom zachowania mechanizmów kontroli zatłoczenia. Rozwijamy oprogramowanie dla architektury klastrowej i analizujemy czasy jego działania, ilość komunikacji, obciążenie każdego z procesorów. Otrzymana aplikacja jest skalowalna i daje znaczące przyśpieszenie oraz efektywność.
5
Content available remote How to Compute Times of Random Walks based Distributed Algorithms
Bui A., Sohier D.
Fundamenta Informaticae
|
2007
|
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.
6
Content available remote An Efficient Message Passing Election Algorithm based on Mazurkiewicz's Algorithm
Chalopin J., Métivier Y.
Fundamenta Informaticae
|
2007
|
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.
7
Content available remote Leader election in rings with nonunique labels
Dobrev S., Pelc A.
Fundamenta Informaticae
|
2004
|
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.
8
Content available remote Integrating Distributed Algorithms into distributed systems
Kindler E., Peuker S.
Fundamenta Informaticae
|
1999
|
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.
9
Content available remote ILF and DAWN for verifying distributed algorithms : an idea for a tool
Baar T., Kindler E.
Fundamenta Informaticae
|
1999
|
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.
10
Content available remote Randomized enumeration
Dembiński P.
Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
|
1998
|
nr 848
1-17
PL
W pracy zaproponowano probabilistyczną wersję rozproszonego algorytmu numeracji węzłów sieci procesów. Zaletą tego probabilistycznego podejścia jest to, że wynikowy algorytm poprawnie numeruje węzły sieci o dowolnej topologii i może być całkowicie asynchroniczny (w przypadku deterministycznych rozwiązań obie te cechy mają pewne ograniczenia). Przebadano zarówno poprawność zaproponowanego algorytmu jak i jego efektywność. Te ostatnią szacuje sie poprzez oczekiwaną liczbę 'rund', w terminach których zdefiniowano algorytm. Okazuje się, że ta oczekiwana wartość jest bliska jedynce, a to znaczy, że czas wykonania algorytmu jest w praktyce równy maksymalnemu czasowi przepływu informacji pomiędzy węzłami rozpatrywanej sieci. Algorytm został opisany w języku specyfikacji Estelle. Eksperymenty symulacyjne (wykonywane zarówno dla deterministycznych jak i probabilistycznych specyfikacji algorytmu w tym formalizmie) potwierdziły otrzymane rezultaty.
EN
The paper describes a randomized version of the distributed enumeration algorithm (protocol) in a network of processes. The advantage of the randomized approach is in that the resulting algorithm works for all network topologies and for fully asynchronous communication (which is not the case for the deterministic case). Correctness of the protocol is examined as well its efficiency. The latter is estimated in probabilistic terms by means of the expected number of 'drawing rounds' in which the algorithm is defined. The value is shown to be close to one and it means that practically the algorithm is performed in time needed to broadcast a message in the network. The algorithm is implemented in the specification language Estelle. Simulation experiments (with both deterministic and randomized Estelle specifications) confirmed the obtained results.
11
Content available remote Randomized enumeration
Dembiński P.
Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
|
1998
|
nr 848
1-17
12
Content available remote New trends in parallel and distributed evolutionary computing
Seredyński F.
Fundamenta Informaticae
|
1998
|
Vol. 35, nr 1-4
211-230
EN
The paper overviews existing models and new tendencies observed in the current literature concerning parallel and distributed evolutionary computation. Sources of parallelism, ways of exploring it and forms of a distributed control of execution of parallel evolutionary algorithms are discussed. Some taxonomy of parallel and distributed computation is proposed. The most known or promising computational schemes are overviewed.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.