We consider the problem of simulating a k-valued register in a wait-free manner using binary registers as building blocks, where k 2. We show that for any simulation using atomic binary base registers to simulate a safe k-valued register in which the read algorithm takes the optimal number of steps (log2 k), the write algorithm must take at least log2 k steps in the worst case. A fortiori, the same lower bound applies when the simulated register should be regular. Previously known algorithms show that both these lower bounds are tight. We also show that in order to simulate an atomic k-valued register for two readers, the optimal number of steps for the read algorithm must be strictly larger than log2 k.

A software obfuscator is a program O to transform a source program P for protection against malicious reverse engineering. O should be correct (O(P) has same functionality with P), resilient (O(P) is resilient against attacks), and effective (O(P) is not too much slower than P). In this paper we describe the design of an obfuscator which consists of two parts. The first part extracts the control flow information from the program and saves it in another process named Monitor-process. The second part protects Monitor-process converting it into an Aucsmith like self-modifying version. We prove the correctness of the obfuscation scheme. We assess its resilience and efficiency to show that both are This supports the claim that our approach is practical.

We prove tight bounds on the time needed to solve k-set agreement . In this problem, each processor starts with an arbitrary input value taken from a fixed set, and halts after choosing an output value. In every execution, at most k distinct output values may be chosen, and every processor's output value must be some processor's input value. We analyze this problem in a synchronous, message-passing model where processors fail by crashing. We prove a lower bound of ⌊f/k⌋+1 degree of coordination required, and the number of faults tolerated, even in idealized models like the synchronous model. The proof of this result is interesting because it is the first to apply topological techniques to the synchronous model.

To enhance performance on shared memory multiprocessors, various techniques have been proposed to reduce the latency of memory accesses, including pipelining of accesses, out-of-order execution of accesses, and branch prediction with speculative execution. These optimizations can, however, complicate the user's model of memory. This paper attacks the problem of simplifying programming on two fronts. First, a general framework is presented for defining shared memory consistency conditions that allows nonsequential execution of memory accesses. The interface at which conditions are defined is between the program and the system and is architecture-independent. The framework is used to generalize three consistency conditions---sequential consistency, hybrid consistency, and weak consistency---for nonsequential execution. Thus, familiar consistency conditions can be precisely specified even in optimized architectures. Second, three techniques are described for structuring programs so that a shared memory that provides the weaker (and more efficient) condition of hybrid consistency appears to guarantee the stronger (and more costly) condition of sequential consistency. The benefit of these techniques is that sequentially consistent executions are easier to reason about. The first technique statically classifies accesses based on their type. This approach is extremely simple to use and leads to a general technique for writing efficient synchronization code. The third technique is to avoid data races in the program, which was previously studied in a somewhat different setting. Precise, yet short and comprehensible, proofs are provided for the correctness of the programming techniques. Such proofs shed light on the reasons these techniques work; we believe that the insight gained can lead to the development of other techniques.

No abstract available.

A fundamental aspect of any concurrent system is how processes communicate with each other. Ultimately, all communication involves concurrent reads and writes of shared memory cells, or registers The stronger the guarantees provided by a register, the more useful it is to the user, but the harder it may be to implement in practice. This paper considers the problem of implementing a k-ary regular (respectively, safe) register out of binary regular (respectively, safe) registers, assuming a single writer. While algorithms have been developed previously for these problems, no nontrivial lower bounds were known. The cost measures considered here are the number of physical registers and the number of reads and writes on the physical registers required to implement the logical register. Tight bounds are obtained on the cost measures in many cases, and interesting trade-offs between the cost measures are identified. The lower bounds are shown using information-theoretic techniques. Two new algorithms are presented that improve on the costs of previously known algorithms: the hypercube algorithm implements a k-ary safe register out of binary safe registers, requiring only one physical write per logical write; and the tree algorithm implements a k-ary regular register out of binary regular registers, requiring only $\lceil {\log k} \rceil $ physical operations per logical operation. Both algorithms use novel combinatorial techniques.

We prove tight bounds on the time needed to solve k-set agreement, a natural generalization of consensus. We analyze this problem in a synchronous, message-passing model where processors fail by crashing. We prove a lower bound of [f/k]+1 rounds of communication for solutions to k-set agreement that tolerate f failures. This bound is tight, and shows that there is an inherent tradeoff between the running time, the degree of coordination required, and the number of faults tolerated, even in idealized models like the synchronous model. The proof of this result is interesting because it is a geometric combination of other well-known proof techniques.>

Much of modernsystems programming involves designing algorithms for distributed systems in which the nodes have access to information about time.Time information can be used to estimate the time at which system or environment events occur, to detect process failures, to schedule the use of

Article Free Access Share on Shared memory consistency conditions for non-sequential execution: definitions and programming strategies Authors: Hagit Attiya View Profile , Soma Chaudhuri View Profile , Roy Friedman View Profile , Jennifer L. Welch View Profile Authors Info & Claims SPAA '93: Proceedings of the fifth annual ACM symposium on Parallel Algorithms and ArchitecturesAugust 1993 Pages 241–250https://doi.org/10.1145/165231.165263Published:01 August 1993Publication History 10citation357DownloadsMetricsTotal Citations10Total Downloads357Last 12 Months7Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We define the k-set consensus problem as an extension of the consensus problem, where each processor decides on a single value such that the set of decided values in any run is of size at most k.We study variations of this problem by adding the agreement condition, which requires that any decided value must be an initial value of some processor, and the uncertainty condition, which requires that there must be some initial configuration from which all possible input values can be decided.While the basic set consensus problem has an (n -1) -resilient protocol, adding the agreement condition only yields a (k-1)-resilient protocol.We prove using a combinatorial argument that any k-resilient protocol for the latter problem would satisfy the uncertainty condition, while this is not true for a (k -I)-resilient pro+ col.This seems to strengthen the conjecture that there is no k-resilient protocol for this problem.Our motivation for studying this class of problems is to test whether the number of choices allowed to the processors is related to the number of faults.We hope that this will provide intuition towards achieving better bounds for more practical problems that arise in distributed comput-+Supported by NSF grant rto.

We describe a polynomial time algorithm that, for every input graph, either outputs the minimum bisection of the graph or halts without output. More importantly, we show that the algorithm chooses the former course with high probability for many natural classes of graphs. In particular, for every fixed d⩾3, all suffciently large n and all b = o(n1-(1/[(d+1)/2]), the algorithm finds the minimum bisection for almost all d-regular labelled simple graphs with 2n nodes and bisection width b.