Atomic (linearizable) read/write memory is a fundamental abstractions in distributedcomputing. Following a seminal implementation of atomic memory of Attiya et al.[6], a folklore belief developed that in messaging-pa...
详细信息
ISBN:
(纸本)9781595939890
Atomic (linearizable) read/write memory is a fundamental abstractions in distributedcomputing. Following a seminal implementation of atomic memory of Attiya et al.[6], a folklore belief developed that in messaging-passing atomic memory implementations "reads must write." However, work by Dutta et al.[4] established that if the number of readers R is constrained with respect to the number of replicas S and the maximum number of crash-failures t so that R
Consider a distributed systems S of sensors, where the goal is to continuously output an agreed reading. The input readings of non-faulty sensors may changed over time;and some of the sensors may be faulty (Byzantine)...
详细信息
ISBN:
(纸本)9781595939890
Consider a distributed systems S of sensors, where the goal is to continuously output an agreed reading. The input readings of non-faulty sensors may changed over time;and some of the sensors may be faulty (Byzantine). Thus, the system is required to repeatedly perform consensus oil the input values. This paper investigates the following question: assuming. the input, values of all the non-faulty sensors remain unchanged for a long period of time, what can be said,about the agreed-upon output reading of the entire system. We prove that no system's output is stable, i.e. the faulty sensors call force a change of the output value at least once. We show that any system with binary input values can avoid changing its output, more than once, thus matching the lower bound. For systems with multi-value inputs, we show that, the output may change at most twice;when n = 3f + 1 this solution is shown to be tight. Moreover, the solutions we Present, are self-stabilizing.
We consider the worst-case remote memory reference (RMR) complexity of first-come-first-served (FCFS) mutual exclusion (ME) algorithms for N asynchronous reliable processes, that communicate only by reading and writin...
详细信息
ISBN:
(纸本)9781595939890
We consider the worst-case remote memory reference (RMR) complexity of first-come-first-served (FCFS) mutual exclusion (ME) algorithms for N asynchronous reliable processes, that communicate only by reading and writing shared memory. We exhibit an upper bound of O(log N) RMRs for FCFS ME, which is tight, improves on prior results, and matches a lower bound for ME (with or without FCFS).
This paper studies the problem of computing the most frequent, element, (the mode) by means of a distributed algorithm where the elements are located at the nodes of a network. Let k denote, the number of distinct ele...
详细信息
ISBN:
(纸本)9781595939890
This paper studies the problem of computing the most frequent, element, (the mode) by means of a distributed algorithm where the elements are located at the nodes of a network. Let k denote, the number of distinct elements and further let m(i) be the number of occurrences of the element e(i) in the ordered list;of occurrences m(1) > m(2) >= ... >= m(k). We give a deterministic distributed algorithm with time complexity O(D+k) where D denotes the diameter of the graph, which is essentially flight. As our main contribution, a Monte Carlo algorithm is presented which computes the mode in O(D + F-2/m(1)(2) . log k) time with high probability, where the frequency moment Fe is defined as F-l = Sigma(k)(i=1) m(i)(l). This algorithm is substantially faster than the deterministic algorithm for various relevant frequency distributions. Moreover, we provide a lower bound of Omega(D + F-5/(m(1)(5)B)), where B is the maximum message size, that captures the effect of the frequency distribution oil the time complexity to compute the mode.
This paper studies the fundamental trade-off between communication cost and delay cost arising in Various contexts such as control message aggregation or organization theory. An optimization problem is considered wher...
详细信息
ISBN:
(纸本)9781595939890
This paper studies the fundamental trade-off between communication cost and delay cost arising in Various contexts such as control message aggregation or organization theory. An optimization problem is considered where nodes are organized in a tree topology. The nodes seek to minimize the time until the root is informed about their states and to use as few transmissions as possible at the same time. We derive all upper bound on the competitive ratio of O(min(h, c)) where h is the tree's height, and c is the transmission cost per edge. Moreover, we prove that this upper bound is tight in the sense that any oblivious algorithm has a ratio of at least Omega(min(h, c)). For chain networks, we prove a tight competitive ratio of Theta(min(root h, c)). Furthermore, the paper introduces a new model for online event aggregation where the importance of ail event depends oil its difference to previous events.
We consider six classes of linear pipeline configuration problems with different mapping objectives and network constraints in distributed heterogeneous computing environments. We prove that two of them are polynomial...
详细信息
ISBN:
(纸本)9781595939890
We consider six classes of linear pipeline configuration problems with different mapping objectives and network constraints in distributed heterogeneous computing environments. We prove that two of them are polynomially solvable and the rest are NP-complete, for each of which, an optimal or heuristic algorithm based on dynamic programming is designed. Extensive simulation results illustrate the efficacy of these algorithms in comparison with existing methods.
In this paper, we propose a simple and optimal causal broadcast protocol which copes with the dynamically changing groups in mobile environments. The protocol depends on two simples, yet powerful ideas. The first cons...
详细信息
ISBN:
(纸本)9781595939890
In this paper, we propose a simple and optimal causal broadcast protocol which copes with the dynamically changing groups in mobile environments. The protocol depends on two simples, yet powerful ideas. The first consists in the use of the immediate dependency relationship (IDR) in the construction of control information (CI), resulting in O(1) message overhead. When the second original idea consists in considering the join/leave requests as data messages. This ensures a consistent perception within a group and makes no need to a coordination phase in the installation of a view.
In this paper, we sketch a novel gossip-based scheme that allows all the nodes in an n-node overlay network to compute a common aggregate (MAX) of their values using O(n log log n) messages within O(log n) rounds of c...
详细信息
ISBN:
(纸本)9781595939890
In this paper, we sketch a novel gossip-based scheme that allows all the nodes in an n-node overlay network to compute a common aggregate (MAX) of their values using O(n log log n) messages within O(log n) rounds of communication. Our result is achieved relaxing the hypothesis that nodes are address-oblivious, raising the question whether this paradigm (address-aware) is more expressive than the address-oblivious one.
We design a stateless and distributed solution to the problem of maximum multicommodity flows-route the maximum amount of flow between given source-sink pairs, possibly split along several paths, subject to edge-capac...
详细信息
ISBN:
(纸本)9781595939890
We design a stateless and distributed solution to the problem of maximum multicommodity flows-route the maximum amount of flow between given source-sink pairs, possibly split along several paths, subject to edge-capacity constraints. Our main contribution is in extending the work of [1, 2] to the case where the flow can be routed along possibly exponentially many different paths. Our algorithm, stalling from an arbitrary feasible flow, always maintains a feasible flow, and reaches a 1 + ∈ approximation of maximum benefit value in Õ(n2) rounds.
Consider an asynchronous system with private channels and n processes, up to t of which may be faulty. We settle a long-standing open question by providing a Byzantine agreement protocol that simultaneously achieves t...
详细信息
ISBN:
(纸本)9781595939890
Consider an asynchronous system with private channels and n processes, up to t of which may be faulty. We settle a long-standing open question by providing a Byzantine agreement protocol that simultaneously achieves three properties: 1. (optimal) resilience: it works as long as n > 3t;2. (almost-sure) termination: with probability one, all nonfaulty processes terminate;3. (polynomial) efficiency: the expected computation time. memory, consumption, message size, and number of messages sent, are all polynomial in n. Earlier protocols have achieved only two of these three properties. In particular, the protocol of Bracha is not polynomially efficient, the protocol of Feldman and Micali is not optimally resilient, and the protocol of Canetti and Rabin does not, have almost-sure termination. Our protocol utilizes a new primitive called shunning (asynchronous) verifiable secret slaving (SVSS). which ensures, roughly speaking, that. either a secret is successfully shared or a new faulty process is ignored from this point onwards by some process.
暂无评论