Distributed Computing

Công bố khoa học tiêu biểu

* Dữ liệu chỉ mang tính chất tham khảo

Sắp xếp:  
Synchronous Byzantine quorum systems
Distributed Computing - Tập 13 - Trang 45-52 - 2000
Rida A. Bazzi
Quorum systems have been used to implement many coordination problems in distributed systems such as mutual exclusion, data replication, distributed consensus, and commit protocols. Malkhi and Reiter recently proposed quorum systems that can tolerate Byzantine failures; they called these systems Byzantine quorum systems and gave some examples of such quorum systems. In this paper, we propose a new definition of Byzantine quorums that is appropriate for synchronous systems. We show how these quorums can be used for data replication and propose a general construction of synchronous Byzantine quorums using standard quorum systems. We prove tight lower bounds on the load of synchronous Byzantine quorums for various patterns of failures and we present synchronous Byzantine quorums that have optimal loads that match the lower bounds for two failure patterns.
A time complexity lower bound for adaptive mutual exclusion
Distributed Computing - - 2012
Yong Jik Kim, James H. Anderson
Distributed speculative execution for reliability and fault tolerance: an operational semantics
Distributed Computing - Tập 21 - Trang 433-455 - 2008
Cristian Ţăpuş, Jason Hickey
This paper examines the use of speculations, a form of distributed transactions, for improving the reliability and fault tolerance of distributed systems. A speculation is defined as a computation that is based on an assumption that is not validated before the computation is started. If the assumption is later found to be false, the computation is aborted and the state of the program is rolled back; if the assumption is found to be true, the results of the computation are committed. The primary difference between a speculation and a transaction is that a speculation is not isolated—for example, a speculative computation may send and receive messages, and it may modify shared objects. As a result, processes that share those objects may be absorbed into a speculation. We present a syntax, and an operational semantics in two forms. The first one is a speculative model, which takes full advantage of the speculative features. The second one is a nonspeculative, nondeterministic model, where aborts are treated as failures. We prove the equivalence of the two models, demonstrating that speculative execution is equivalent to failure-free computation.
Special issue with selected papers from DISC 2012
Distributed Computing - Tập 27 - Trang 391-391 - 2014
Marcos K. Aguilera
Implementing the CORBA GIOP in a high-performance object request broker environment
Distributed Computing - - 2001
Geoff Coulson, Shakuntala Baichoo
Verification of multiprocess probabilistic protocols
Distributed Computing - Tập 1 - Trang 53-72 - 1986
Amir Pnueli, Lenore Zuck
In this paper we demonstrate the utility of temporal logic to the formal verification of probabilistic distributed programs. The approach taken is to represent the quantitative notion of probabilistic computations by the qualitative abstraction ofextreme fairness. The method is illustrated first on the dining philosophers problem [3] and then on a new probabilistic symmetric solution to then-processes mutual exclusion problem. Two related solutions are presented corresponding to different assumptions about the granularity of a compound test.
Techniques and applications of computation slicing
Distributed Computing - Tập 17 Số 3 - Trang 251-277 - 2005
Neeraj Mittal, Vijay K. Garg
Wait-freedom with advice
Distributed Computing - Tập 28 - Trang 3-19 - 2014
Carole Delporte-Gallet, Hugues Fauconnier, Eli Gafni, Petr Kuznetsov
We motivate and propose a new way of thinking about failure detectors which allows us to define what it means to solve a distributed task wait-free using a failure detector. In our model, the system is composed of computation processes that obtain inputs and are supposed to produce outputs and synchronization processes that are subject to failures and can query a failure detector. Under the condition that correct (never failing) synchronization processes take sufficiently many steps, they provide the computation processes with enough advice to solve the given task wait-free: every computation process outputs in a finite number of its own steps, regardless of the behavior of other computation processes. Every task can thus be characterized by the weakest failure detector that allows for solving it, and we show that every such failure detector captures a form of set agreement. We then obtain a complete classification of tasks, including ones that evaded comprehensible characterization so far, such as renaming or weak symmetry breaking.
Meeting in a polygon by anonymous oblivious robots
Distributed Computing - Tập 33 - Trang 445-469 - 2019
Giuseppe Antonio Di Luna, Paola Flocchini, Nicola Santoro, Giovanni Viglietta, Masafumi Yamashita
The Meeting problem for $$k\ge 2$$ searchers in a polygon P (possibly with holes) consists in making the searchers move within P, according to a distributed algorithm, in such a way that at least two of them eventually come to see each other, regardless of their initial positions. The polygon is initially unknown to the searchers, and its edges obstruct both movement and vision. Depending on the shape of P, we minimize the number of searchers k for which the Meeting problem is solvable. Specifically, if P has a rotational symmetry of order $$\sigma $$ (where $$\sigma =1$$ corresponds to no rotational symmetry), we prove that $$k=\sigma +1$$ searchers are sufficient, and the bound is tight. Furthermore, we give an improved algorithm that optimally solves the Meeting problem with $$k=2$$ searchers in all polygons whose barycenter is not in a hole (which includes the polygons with no holes). Our algorithms can be implemented in a variety of standard models of mobile robots operating in Look–Compute–Move cycles. For instance, if the searchers have memory but are anonymous, asynchronous, and have no agreement on a coordinate system or a notion of clockwise direction, then our algorithms work even if the initial memory contents of the searchers are arbitrary and possibly misleading. Moreover, oblivious searchers can execute our algorithms as well, encoding information by carefully positioning themselves within the polygon. This code is computable with basic arithmetic operations (provided that the coordinates of the polygon’s vertices are algebraic real numbers in some global coordinate system), and each searcher can geometrically construct its own destination point at each cycle using only a compass and a straightedge. We stress that such memoryless searchers may be located anywhere in the polygon when the execution begins, and hence the information they initially encode is arbitrary. Our algorithms use a self-stabilizing map construction subroutine which is of independent interest.
Special issue on PODC 2009
Distributed Computing - Tập 24 - Trang 1-1 - 2011
Lorenzo Alvisi
Tổng số: 554   
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 10