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:
Combinatorial algorithms for distributed graph coloring
Distributed Computing - Tập 27 - Trang 79-93 - 2013
Numerous problems in Theoretical Computer Science can be solved very efficiently using powerful algebraic constructions. Computing shortest paths, constructing expanders, and proving the PCP Theorem, are just few examples of this phenomenon. The quest for combinatorial algorithms that do not use heavy algebraic machinery, but are roughly as efficient, has become a central field of study in this ar...... hiện toàn bộ
Communication-efficient randomized consensus
Distributed Computing - Tập 31 - Trang 489-501 - 2017
We consider the problem of consensus in the challenging classic model. In this model, the adversary is adaptive; it can choose which processors crash at any point during the course of the algorithm. Further, communication is via asynchronous message passing: there is no known upper bound on the time to send a message from one processor to another, and all messages and coin flips are seen by the ad...... hiện toàn bộ
A knowledge-theoretic analysis of uniform distributed coordination and failure detectors
Distributed Computing - Tập 17 - Trang 223-236 - 2005
It is shown that, in a precise sense, if there is no bound on the number of faulty processes in a system with unreliable but fair communication, Uniform Distributed Coordination (UDC) can be attained if and only if a system has perfect failure detectors. This result is generalized to the case where there is a bound t on the number of faulty processes. It is shown that a certain type of generalized...... hiện toàn bộ
Exhaustive analysis and simulation for distributed systems, both sides of the same coin
Distributed Computing - Tập 2 - Trang 213-225 - 1988
This paper presents exhaustive analysis and simulation for distributed systems validation. Exhaustive analysis makes possible to detect quickly several types of errors, for instance, unspecified reception of signals, errors in timer management, deadlock, errors in precedence, etc. But, in general, exhaustive analysis can only be applied to a simplified model of the distributed system due to the st...... hiện toàn bộ
Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication
Distributed Computing - Tập 30 - Trang 339-355 - 2015
Distributed computing models typically assume reliable communication between processors. While such assumptions often hold for engineered networks, e.g., due to underlying error correction protocols, their relevance to biological systems, wherein messages are often distorted before reaching their destination, is quite limited. In this study we take a first step towards reducing this gap by rigorou...... hiện toàn bộ
Close to linear space routing schemes
Distributed Computing - Tập 29 - Trang 65-74 - 2015
Let
$$G=(V,E)$$
be an unweighted undirected graph with n vertices and m edges, and let
$$k>2$$
...... hiện toàn bộ
On the complexity of global computation in the presence of link failures: the general case
Distributed Computing - Tập 8 - Trang 115-120 - 1995
This paper presents Ω(m logn) and Ω(mn) messages lower bounds on the problem of computing a gobal sensitive function in biderectional networks with link failures (i.e., dynamically changing topology), wheren andm are the total number of nodes and links in the network. The Ω(m logn) lower bound is under the assumption thatn is a-priori known to the nodes, while the second bound is for the case in w...... hiện toàn bộ
An adaptive collect algorithm with applications
Distributed Computing - Tập 15 - Trang 87-96 - 2002
In a shared-memory distributed system, n independent asynchronous processes communicate by reading and writing to shared variables. An algorithm is adaptive (to total contention) if its step complexity depends only on the actual number, k, of active processes in the execution; this number is unknown in advance and may change in different executions of the algorithm. Adaptive algorithms are inhere...... hiện toàn bộ
Maximum throughput of multiple access channels in adversarial environments
Distributed Computing - Tập 22 - Trang 93-116 - 2009
We consider deterministic distributed broadcasting on multiple access channels in the framework of adversarial queuing. Packets are injected dynamically by an adversary that is constrained by the injection rate and the number of packets that may be injected simultaneously; the latter we call burstiness. A protocol is stable when the number of packets in queues at the stations stays bounded. The ma...... hiện toàn bộ
Competitive throughput in multi-hop wireless networks despite adaptive jamming
Distributed Computing - Tập 26 Số 3 - Trang 159-171 - 2013
This article presents a simple local medium access control protocol, called Jade, for multi-hop wireless networks with a single channel that is provably robust against adaptive adversarial jamming. The wireless network is modeled as a unit disk graph on a set of nodes distributed arbitrarily in the plane. In addition to these nodes, there are adversarial jammers that know the protocol and its enti...... hiện toàn bộ
Tổng số: 554
- 1
- 2
- 3
- 4
- 5
- 6
- 10