We study the renaming problem in a fully connected synchronous network with Byzantine failures. We show that when the original namespace of the processors is unbounded, this problem cannot be solved in an a priori bou...
详细信息
We study the renaming problem in a fully connected synchronous network with Byzantine failures. We show that when the original namespace of the processors is unbounded, this problem cannot be solved in an a priori bounded number of rounds for t >= (n + n mod 3)/3, where n is the size of the network and t is the number of failures. On the other hand, for n > 3t, we present a Byzantine renaming algorithm that runs in O(lg n) rounds. In addition, we present a fast, efficient strong renaming algorithm for n > t, which runs in O(n lg(2) [N-0/n]) rounds, where N-0 is the value of the highest identifier among all the correct processors.
We investigate a metric facility location problem in a distributed setting. In this problem, we assume that each point is a client as well as a potential location for a facility and that the opening costs for the faci...
详细信息
We investigate a metric facility location problem in a distributed setting. In this problem, we assume that each point is a client as well as a potential location for a facility and that the opening costs for the facilities and the demands of the clients are uniform. The goal is to open a subset of the input points as facilities such that the accumulated cost for the whole point set, consisting of the opening costs for the facilities and the connection costs for the clients, is minimized. We present a randomized distributed algorithm that computes in expectation an -approximate solution to the metric facility location problem described above. Our algorithm works in a synchronous message passing model, where each point is an autonomous computational entity that has its own local memory and that communicates with the other entities by messagepassing. We assume that each entity knows the distance to all the other entities, but does not know any of the other pairwise distances. Our algorithm uses three rounds of all-to-all communication with message sizes bounded to bits, where n is the number of input points. We extend our distributed algorithm to constant powers of metric spaces. For a metric exponent a""a parts per thousand yen1, we obtain a randomized -approximation algorithm that uses three rounds of all-to-all communication with message sizes bounded to bits.
Decision tasks require that nonfaulty processes make decisions based on their input values. Simultaneous decision tasks require that nonfaulty processes decide in the same round. Most decision tasks have known worst-c...
详细信息
ISBN:
(纸本)9781450307192
Decision tasks require that nonfaulty processes make decisions based on their input values. Simultaneous decision tasks require that nonfaulty processes decide in the same round. Most decision tasks have known worst-case lower bounds. Most also have known worst-case optimal protocols that halt in the number of rounds given by the worst-case lower bound, and some have early-stopping protocols that can halt earlier than the worst-case lower bound (sometimes in as early as two rounds). We consider what might be called earliest-possible protocols for simultaneous decision tasks. We present a new technique that converts worst-case optimal decision protocols into all-case optimal simultaneous decision protocols: For every behavior of the adversary, the all-case optimal protocol decides as soon as any protocol can decide in a run with the same adversarial behavior. Examples to which this can be applied include set consensus, condition-based consensus, renaming and order-preserving renaming. Some of these tasks can be solved significantly faster than the classical simultaneous consensus task. A byproduct of the analysis is a proof that improving on the worst-case bound for any simultaneous task by even a single round is as hard as reaching simultaneous consensus.
暂无评论