The proceedings contains 43 papers. Topics discussed include distributedcomputing, time complexity, concurrent distributed queuing, quorum systems probes, abstraction, cone-based distributed topology control algorith...
详细信息
The proceedings contains 43 papers. Topics discussed include distributedcomputing, time complexity, concurrent distributed queuing, quorum systems probes, abstraction, cone-based distributed topology control algorithm, hybrid mix networks and semantic reasoning.
The distributed (Delta + 1)-coloring problem is one of the most fundamental and well-studied problems in distributed algorithms. Starting with the work of Cole and Vishkin in 1986, a long line of gradually improving a...
详细信息
The distributed (Delta + 1)-coloring problem is one of the most fundamental and well-studied problems in distributed algorithms. Starting with the work of Cole and Vishkin in 1986, a long line of gradually improving algorithms has been published. The state-of-the-art running time, prior to our work, is O(Delta log Delta + log* n), due to Kuhn and Wattenhofer [proceedings of the 25th annualacmsymposium on principles of distributedcomputing, Denver, CO, 2006, pp. 7-15]. Linial [proceedings of the 28th annual IEEE symposium on Foundation of Computer Science, Los Angeles, CA, 1987, pp. 331-335] proved a lower bound of 1/2 log* n for the problem, and Szegedy and Vishwanathan [proceedings of the 25th annualacmsymposium on Theory of computing, San Diego, CA, 1993, pp. 201-207] provided a heuristic argument that shows that algorithms from a wide family of locally iterative algorithms are unlikely to achieve a running time smaller than Theta(Delta log Delta). We present a deterministic (Delta + 1)-coloring distributed algorithm with running time O(Delta) + 1/2 log* n. We also present a trade-off between the running time and the number of colors, and devise an O(***)-coloring algorithm, with running time O(Delta/lambda + log* n), for any parameter lambda > 1. Our algorithm breaks the heuristic barrier of Szegedy and Vishwanathan and achieves running time which is linear in the maximum degree Delta. On the other hand, the conjecture of Szegedy and Vishwanathan may still be true, as our algorithm does not belong to the family of locally iterative algorithms. On the way to this result we study a generalization of the notion of graph coloring, which is called defective coloring [L. Cowen, R. Cowen, and D. Woodall, J. Graph Theory, 10 (1986), pp. 187-195]. In an m-defective p-coloring the vertices are colored with p colors so that each vertex has up to m neighbors with the same color. We show that an m-defective p-coloring with reasonably small m and p can be compute
We determine the weakest failure detector to solve nonuniform consensus in any environment, i.e., regardless of the number of faulty processes. Together with previous results, this closes all aspects of the following ...
详细信息
ISBN:
(纸本)9781581139945
We determine the weakest failure detector to solve nonuniform consensus in any environment, i.e., regardless of the number of faulty processes. Together with previous results, this closes all aspects of the following question: What is the weakest failure detector to solve (uniform or nonuniform) consensus in any environment?
This paper is an answer to the question: 'What is unique and conceptually different about mobile computing?' The paper begins by describing a set of constraints intrinsic to mobile computing, and examining the...
详细信息
ISBN:
(纸本)9780897918008
This paper is an answer to the question: 'What is unique and conceptually different about mobile computing?' The paper begins by describing a set of constraints intrinsic to mobile computing, and examining the impact of these constraints on the design of distributed systems. Next, it summarizes the key results of the Coda and Odyssey systems. Finally, it describes the research opportunities in five important topics relevant to mobile computing: caching metrics, semantic callbacks and validators, resource revocation, analysis of adaptation, and global estimation from local observations.
A two-level model of distributed computation based on actors is presented. This model is the basis for developing a semantic framework supporting dynamic customizability and separation of concerns in designing and rea...
详细信息
ISBN:
(纸本)9780897917100
A two-level model of distributed computation based on actors is presented. This model is the basis for developing a semantic framework supporting dynamic customizability and separation of concerns in designing and reasoning with respect to the components of open distributed systems (ODS). This paper focuses on remote creation, migration, and reachability as well as their specification at different levels of abstraction and their composition.
暂无评论