In 2004, Klavins et al. introduced the use of graph grammars to describe-and to program-systems of self-assembly. It turns out that these graph grammars can be embedded in a graph rewriting characterization of distrib...
详细信息
ISBN:
(纸本)9781605583969
In 2004, Klavins et al. introduced the use of graph grammars to describe-and to program-systems of self-assembly. It turns out that these graph grammars can be embedded in a graph rewriting characterization of distributed systems that was proposed by Degano and Montanari over twenty years ago. By applying techniques obtained from this observation, we prove a generalized version of Soloveichik and Winfree's theorem on local determinism. We also obtain a canonical method to simulate asynchronous constant-size-message-passing models of distributedcomputing with systems of self-assembly.
The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph G and a spanning tree T for it, and the goal is to augment T with a minimum set of edges Aug from G, such that...
详细信息
The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph G and a spanning tree T for it, and the goal is to augment T with a minimum set of edges Aug from G, such that T boolean OR Aug is 2-edge-connected. TAP has been widely studied in the sequential setting. The best known approximation ratio of 2 for the weighted case dates back to the work of Frederickson and JaJa (SIAM J Comput 10(2):270-283, 1981). Recently, a 3/2-approximation was given for unweighted TAP by Kortsarz and Nutov (acm Trans Algorithms 12(2):23, 2016). Recent breakthroughs give an approximation of 1.458 for unweighted TAP (Grandoni et al. in: proceedings of the 50th annualacm SIGACT symposium on theory of computing (STOC 2018), 2018), and approximations better than 2 for bounded weights (Adjiashvili in: proceedings of the twenty-eighth annualacm-SIAM symposium on discrete algorithms (SODA), 2017;Fiorini et al. in: proceedings of the twenty-ninth annualacm-SIAM symposium on discrete algorithms (SODA 2018), New Orleans, LA, USA, 2018. 10.1137/1.9781611975031.53). In this paper, we provide the first fast distributed approximations for TAP. We present a distributed 2-approximation for weighted TAP which completes in O(h) rounds, where h is the height of T. When h is large, we show a much faster 4-approximation algorithm for the unweighted case, completing in O(D+root nlog*n) rounds, where n is the number of vertices and D is the diameter of G. Immediate consequences of our results are an O(D)-round 2-approximation algorithm for the minimum size 2-edge-connected spanning subgraph, which significantly improves upon the running time of previous approximation algorithms, and an O(h(MST)+root nlog*n)-round 3-approximation algorithm for the weighted case, where h(MST) is the height of the MST of the graph. Additional applications are algorithms for verifying 2-edge-connectivity and for augmenting the connectivity of any connected spanning subgraph to 2.
The most significant strategic development in information technology over the past year has been 'trusted computing'. This is popularly associated with Microsoft's 'Palladium' project, recently ren...
详细信息
The most significant strategic development in information technology over the past year has been 'trusted computing'. This is popularly associated with Microsoft's 'Palladium' project, recently renamed 'NGSCB'. In this paper, I give an outline of the technical aspects of 'trusted computing' and sketch some of the public policy consequences.
The Global Data Computation (GDC) problem in the asynchronous distributedcomputing model where processes are prone to crash failures is addressed. A protocol that solves this problem in an asynchronous distributed sy...
详细信息
The Global Data Computation (GDC) problem in the asynchronous distributedcomputing model where processes are prone to crash failures is addressed. A protocol that solves this problem in an asynchronous distributed system where processes can crash, but equipped with a perfect failure detector is presented. The most important property of the proposed protocol lies in its time optimality.
The 26 papers in this volume deal with principles of distributedcomputing. Topics covered include distributed Networks;Concurrency Controls;distributed Databases;and Operating Systems.
ISBN:
(纸本)0897911105
The 26 papers in this volume deal with principles of distributedcomputing. Topics covered include distributed Networks;Concurrency Controls;distributed Databases;and Operating Systems.
Vertex coloring is one of the classic symmetry breaking problems studied in distributedcomputing. In this paper we present a new algorithm for (Delta+1)-list coloring in the randomized LOCAL model running in O(Det(d)...
详细信息
Vertex coloring is one of the classic symmetry breaking problems studied in distributedcomputing. In this paper we present a new algorithm for (Delta+1)-list coloring in the randomized LOCAL model running in O(Det(d)(polylogn)) time, where Det(d)(n') is the deterministic complexity of (deg+1)-list coloring on n'-vertex graphs. (In this problem, each v has a palette of size deg(v)+1.) This improves upon a previous randomized algorithm of Harris, Schneider, and Su [J. acm, 65 (2018), 19] with complexity O(root log Delta+log log n+Det(d)(poly log n)) = O(root log n). Unless Delta is small, it is also faster than the best known deterministic algorithm of Fraigniaud, Heinrich, and Kosowski [proceedings of the 57th annual IEEE symposium on Foundations of Computer Science (FOCS), 2016] and Barenboim, Elkin, and Goldenberg [proceedings of the 38th annualacmsymposium on principles of distributedcomputing (PODC), 2018], with complexity O(root Delta log log* Delta + log* n). Our algorithm's running time is syntactically very similar to the Omega(Det(poly log n)) lower bound of Chang, Kopelowitz, and Pettie [SIAM J. Comput., 48 (2019), pp. 122-143], where Det(n') is the deterministic complexity of (Delta + 1)-list coloring on n'-vertex graphs. Although distributed coloring has been actively investigated for 30 years, the best determin- istic algorithms for (deg +1)- and (Delta + 1)-list coloring (that depend on n' but not Delta) use a black-box application of network decompositions. The recent deterministic network decomposition algorithm of Rozhoil and Ghaffari [proceedings of the 52nd annualacm SIGACT symposium on Theory of computing (STOC), 2020] implies that Det(d)(n') and Det(n') are both poly(log n'). Whether they are asymptotically equal is an open problem.
The development of algorithms with guaranteed work efficiency for any pattern of fragmentations and merges of the underlying network is addressed. Current results are discussed for the abstract setting where asynchron...
详细信息
The development of algorithms with guaranteed work efficiency for any pattern of fragmentations and merges of the underlying network is addressed. Current results are discussed for the abstract setting where asynchronous processors start performing tasks in isolation and where an adversary can force an arbitrary pattern of merges. Following a merge, processors are able to share their knowledge about the computational progress prior to the merge.
The latest specifications for dynamic group communication in a distributed system are discussed. The reliable broadcast in a dynamic system is called reliable multicast, which is defined by the two primitives rmultica...
详细信息
The latest specifications for dynamic group communication in a distributed system are discussed. The reliable broadcast in a dynamic system is called reliable multicast, which is defined by the two primitives rmulticast and rdeliver. The properties of the reliable multicast include validity, uniform agreement, uniform integrity and uniform same view delivery. For the validity property, if a correct process executes rmulticast(m), then it eventually rdelivers m.
The notions of refinement for branching time based on stuttering simulation and bisimulation are developed. A local proof rule called well-founded simulation is introduced. It is shown that if one system refines anoth...
详细信息
The notions of refinement for branching time based on stuttering simulation and bisimulation are developed. A local proof rule called well-founded simulation is introduced. It is shown that if one system refines another, then a refinement map always exists. The added generality is obtained by using relations to relate implementation states with specification states and by requiring the use of well-founded relations.
暂无评论