We present the δ-Synchronizer, which works in non-synchronous dynamic networks under minimal assumptions. Our model allows for arbitrary topological changes without any guarantee of eventual global or partial stabilization and assumes that nodes are anonymous. This deterministic synchronizer is the first that enables nodes to simulate a dynamic network synchronous algorithm for executions in a semi-synchronous dynamic environment under a weakly-fair node activation scheduler, despite the absence of a global clock, node ids, persistent connectivity or any assumptions about the edge dynamics (in both the synchronous and semi-synchronous environments). We make the following contributions: (1) we extend the definition of synchronizers to networks with arbitrary edge dynamics; (2) we present the first synchronizer from the semi-synchronous to the synchronous model in such networks; and (3) we present non-trivial applications of the proposed synchronizer to existing algorithms. We assume an extension of the Pull communication model by adding a single 1-bit multi-writer atomic register at each edge-port of a node. We show that this extension is needed and that synchronization in our setting is not possible without it. The δ-Synchronizer operates with memory overhead at the nodes that is asymptotically logarithmic on the runtime of the underlying synchronous algorithm being simulated - in particular, it is logarithmic for polynomial-time synchronous algorithms.

Client-side anti-phishing methods are crucial for safeguarding individuals against phishing attacks, offering a proactive approach beyond traditional blocklisting strategies. This study expands the scope to include a comprehensive evaluation of client-side anti-phishing techniques within the Chrome browser, alongside an in-depth analysis of academic research in the field of phishing over the past five years. Our findings highlight the inherent limitations of current client-side anti-phishing measures, which demonstrated a detection rate of only 14% for phishing websites and blocked merely 10% of login-based phishing sites within the first hour, resulting in a substantial false negative rate. Additionally, our analysis reveals that attackers can readily circumvent these defenses by altering the content of phishing websites. The study also critically assesses recent academic contributions to understand their alignment and potential integration with client-side anti-phishing frameworks. Based on these insights, we propose targeted recommendations to enhance the efficacy and responsiveness of the client-side anti-phishing ecosystem, addressing the challenges of low detection coverage, slow response times, and high rates of false negatives.

We consider the problem of supporting payment transactions in an asynchronous system in which up to f validators are subject to Byzantine failures under the control of an adaptive adversary. It was shown that, in the case of a single owner, this problem can be solved without consensus by using byzantine quorum systems (requiring a quorum of 2f + 1 validations per transaction). Nonetheless, the process of validating transactions remains sequential. For example, if one has a balance of ten coins and intends to make separate payments of two coins each to two distinct recipients, both transactions must undergo processing by a common correct validator. On the other hand, these two transactions are non-conflicting as they do not lead to double spending, allowing in principle for parallel validation. In this paper, we show that it is possible to validate payment transactions in parallel with less than f validations per transaction in an asynchronous system, provided that each transaction spends only a small fraction of a balance. Our solution relies on a novel class of probabilistic quorum systems that we introduce in this paper, termed (k1, k2) -quorum systems. In the absence of an adaptive adversary, (k1,k2)-quorum systems can be used to enable concurrent and asynchronous validation of up to k1 transactions while preventing validation of more than k2 transactions. In the presence of an adaptive adversary, at least k1 transactions can be validated concurrently, but validation of more than k′2 > k2 transactions is prevented, with the difference k′2 − k2 dependent on the quorum system's validation slack -- a term defined in this paper. Employing a (k1, k2)-quorum system, we introduce protocols enabling a payer to validate multiple fractional spending transactions in parallel with less than f + 1 validations per transaction. Subsequently, the payer reclaims any remaining funds through a fully validated transaction, referred to as a settlement transaction.

We consider the problem of validating payment transactions in an asynchronous system in which up to f validators are subject to Byzantine failures under the control of an adaptive adversary. It was shown that this problem can be solved without consensus by using byzantine quorum systems - requiring full-quorum validation, i.e. at least 2f + 1 validations per transaction. We show that it is possible to validate transactions in parallel with less than f validations per transaction if each transaction spends no more that a small fraction of an initial balance. Our solution relies on (k1, k2)-quorum systems, a novel class of quorum systems that we introduce in this paper. Under an adaptive adversary, these systems can be used to allow k1 transactions to be validated and prevent more than k′2 > k2 transactions from being validated, the difference k′2 − k2 being dependent on the quorum system's validation slack, which we define in this paper. Using (k1, k2)-quorum systems, a payer can execute multiple partial spending transactions to spend a portion of its initial balance with less than full quorum validation - less than f validations per transaction - then reclaim any remaining funds using one fully validated transaction, which we call a settlement transaction.

Knowledge of structure is critical to map legacy workflows to environments suitable to run on the cloud. We present a method which characterizes a workflow structure with the execution trace produced by instrumented logging functionality. The method generates the structure of workflows to support their reuse by permitting their transformation into modern execution environments. The method presented in the paper is implemented for Python workflows and demonstrated in the context of several legacy scientific workflows.

Imagine that we had a piece of matter that can change its physical properties like shape, density, conductivity, or color in a programmable fashion based on either user input or autonomous sensing. This is the vision behind what is commonly known as programmable matter. Many proposals have already been made for realizing programmable matter, ranging from DNA tiles, shape-changing molecules, and cells created via synthetic biology to reconfigurable modular robotics. We are particularly interested in programmable matter consisting of simple elements called particles that can compute, bond, and move, and the feasibility of solving fundamental problems relevant for programmable matter with these particles. As a model for that programmable matter, we will use a general form of the amoebot model first proposed in SPAA 2014, and as examples of fundamental problems we will focus on leader election and shape formation. For shape formation, we investigate the line formation problem, i.e. we are searching for a local-control protocol so that for any connected structure of particles, the particles will eventually form a line.

We propose a novel and simple approach for securing access to sensitive content on the web. The approach automates the best manual compartmentalization practices for accessing different kinds of content with different browser instances. The automation is transparent to the user and does not require any modification of how non-sensitive content is accessed. For sensitive content, a Fresh Browser Instance (FBI) is automatically created to access the content. Our prototype system Auto-FBI can provide support for novice users with predefined sensitive content sites as well as for more experienced users who can define conflict of interest (COI) classes which allows content from sites in the same user-defined class to coexist in a browser instance. Our initial performance evaluation of Auto-FBI shows that the overhead introduced by the approach is acceptable (less than 160 ms for sites that already have fast load time, but for slow sites the overhead can be as high as 750 ms).

Large datasets and time-consuming processes have become the norm in scientific computing applications. The exploration phase in the development of scientific workflows involves trial-and-error with workflow components, which can take a lot of time given the time-consuming nature of the workflow tasks. These facts suggest the possibility of reducing the development time by reusing intermediate data whenever possible. However the storage space is always limited. This introduces a problem: which intermediate datasets from one workflow should be kept to be reused in another workflow, with a limited amount of storage. For the general class of series parallel graphs, we model this problem using a non-linear integer programming formulation and show that it is NP-Hard. We provide a branch and bound optimal algorithm as well as efficient heuristics. We conducted experiments over a large set of randomly-generated workflows as well as a smaller set of synthetic workflows which are based on real-world workflows used by scientists in different disciplines. Our experiments show that the best solution produced by the heuristics only differs from the optimal value by less than 1% on average.

No abstract available.

In this paper, a CAPTCHA is presented based on the masking characteristics of the human visual system (HVS). Knowing that noise can be masked by high activity regions and showing that edges can be masked by noise for a human observer while still being detected by machines, the suggested CAPTCHA is composed of English alphabets that are picked randomly and written with a combination of texture and edges with added noise such as to deceive the machine by randomly changing the visibility of characters for humans. The proposed CAPTCHA is highly legible and robust to brute-force attacks and sophisticated object character recognition (OCR) segmentation algorithms

The paper presents a reduced-delay selective-ARQ scheme based on a similarity check function that measures the degree of corruption in transmitted multimedia data packets. Accordingly, if the packet is found to be badly corrupted based on a specified similarity criterion, it can be considered as a lost packet and retransmitted. The degree of corruption contributed by a particular packet is measured by the proposed similarity check function at the receiver without explicit knowledge of the original source data. Simulation results and comparisons with a conventional ARQ scheme are provided to illustrate the performance of the proposed method.

No abstract available.

We study ways to restrict or prevent the damage that can be caused in a peer-to-peer network by corrupt entities creating multiple pseudonyms. We show that it is possible to remotely issue certificates that can be used to test the distinctness of identities. To our knowledge, this is the first work that shows that remote anonymous certification of identity is possible under adversarial conditions. Our certification protocols are based on geometric techniques that establish location information in a fault-tolerant and distributed fashion. They do not rely on a centralized certifying authority or infrastructure that has direct knowledge of entities in the system, and work in Euclidean or spherical geometry of arbitrary dimension. Our protocols tolerate corrupt entities, including corrupt certifiers as well as collusion by certification applicants and certifiers. We consider both broadcast and point-to-point message passing models.

This paper introduces the concept of similarity check functions that measure the degree of corruption in transmitted multimedia data packets. Rather than directly discarding or directly retransmitting erroneous packets, the degree of corruption contributed by a particular packet is measured by a similarity check function at the receiver, which does not require explicit knowledge of the source data. Accordingly, if the packet is found to be badly corrupted based on a specified similarity criteria, it can be considered as a lost packet and recovered using forward error correcting codes or retransmission. An example of a similarity check function design and a selective forward error correction (S-FEC) scheme that allocates channel protection bits only to those packets that are in most need of correction, is presented to illustrate the proposed concept.

No abstract available.

We present the first heterogeneous checkpointing scheme for applications using POSIX threads. The scheme relies on source code instrumentation to achieve heterogeneity. It supports various types of synchronization primitives, such as locks, semaphores, condition variables, and join operations. Unlike other non-heterogeneous checkpointing schemes proposed in the literature, our scheme supports both kernel-level and application-level threads executing as part of the same application under various scheduling policies. Also, unlike other non-heterogeneous checkpointing mechanisms proposed in the literature, our solution does not interfere with the semantics of the application and does not use signals. Test results on various hardware platforms running Solaris, Linux, and Windows NT show that the overhead of our scheme is low.

We consider the problem of heterogeneous checkpointing in distributed systems. We propose a new solution to the problem that is truly heterogeneous in that it can support new architectures without any information about the architecture. The ability to support new architectures without additional knowledge or custom configuration is an important contribution of this work. This ability is particularly useful in mobile settings in which there is no a priori knowledge of the potential machines on which the application might execute. Our solution supports execution in unknown settings as long as there is compiler support for the high-level language in which the application is written. We precisely define what it means for a particular solution to be heterogeneous and discuss the heterogeneity of our solution and other solutions. We use code instrumentation at the source code level to provide heterogeneous checkpointing and recovery.

The difficulty of designing fault-tolerant distributed algorithms incr eases with the severity of failures that an algorithm must tolerate, especially for systems with synchronous message passing. This paper considers methods that automatically translate algorithms tolerant of simple crash failures into ones tolerant of more severe failures. These translations simplify the design task by allowing algorithm designers to assume that processors fail only by stopping. Such translations can be quantified by two measures: fault-tolerance , which is a measure of how many processors must remain correct for the translation to be correct, and round-complexity , which is a measure of how the translation increases the running time of an algorithm. Understanding these translations and their limitations with respect to these measures can provide insight into the relative impact of different models of faculty behavior on the ability to provide fault-tolerant applications for systems with synchronous message passing. This paper considers translations fr om crash failures to each of the following types of more severe failures: omission to send messages; omission to send and receive messages; and totally arbitrary behavior. It shows that previously developed translaions to send-omission failures are optimal with respect to both fault-tolerance and round-complexity. It exhibits a hierarchy of translations to general (send/receive) omission failures that improves upon the fault-tolerance of previously developed translations. These translations are optimal in that they cannot be improved with respect to one measure without negatively affecting the other; that is, the hierarchy of translations is matched by corresponding hierarchy of impossibility results. The paper also gives a hierarchy of translations to arbitrary failures that improves upon the round-complexity of previously developed translations. These translations are near-optimal;

Quorum systems have been used to implement many coordination problems in distributed systems such as mutual exclusion, data replication, distributed consensus, and commit protocols. Malkhi and Reiter recently proposed quorum systems that can tolerate Byzantine failures; they called these systems Byzantine quorum systems and gave some examples of such quorum systems. In this paper, we propose a new definition of Byzantine quorums that is appropriate for synchronous systems. We show how these quorums can be used for data replication and propose a general construction of synchronous Byzantine quorums using standard quorum systems. We prove tight lower bounds on the load of synchronous Byzantine quorums for various patterns of failures and we present synchronous Byzantine quorums that have optimal loads that match the lower bounds for two failure patterns.

This paper presents a strong characterization that pre-

The computational power of concurrent data types has been the focus of much recent research. Herlihy showed that such power may be measured by the type’s ability to implement wait-free consensus. Jayanti argued that this ability could be measured in different ways, depending, for example, on whether or not read/write registers could be used in an implementation. He demonstrated the significance of this distinction by exhibiting a nondeterministic type whose ability to implement consensus was increased with the availability of registers. We show that registers cannot increase the ability to implement wait-free consensus of any deterministic type or of any type that can, without them, implement consensus for at least two processes. These results significantly impact the study of the wait-free hierarchies of concurrent data types. In particular, the combination of these results with other recent work suggests that Jayanti’s hm hierarchy is robust for certain classes of deterministic types.

Shared memories that provide weaker consistency guarantees than the traditional sequentially consistent or atomic memories have been claimed to provide the key to building scalable systems.One influential memory model, processor considency, has been cited widely in the literature but, due to the lack of a precise and formal definition, contradictory claims have been made regarding its power.We use a formal model to give two distinct definitions of processors consistency: one corresponding to Goodman's original proposal and the other corresponding that given by the implementors of the DASH system.These definitions are non-operational and can be easily related to other types of memories.To illustrate the power of processor consistency, we exhibit a non-cooperative solution to the mutual exclusion problem that is correct with processor consistency.As a contrast, we show that Lamport's Bakery algorithm is not correct with processor consistency. 1

The problem of fault-tolerant coordination is fundamental in distributed computing. In the past, researchers have considered two types of coordination: general coordination, in which the actions of faulty processors are irrelevant, and consistent coordination, in which the faulty processors are forbidden from acting inconsistently. This paper studies the possibility and complexity of achieving coordination in synchronous and asynchronous systems with crash, send-omission, and general omission failures. We indicate the systems in which coordination cannot be achieved and, when it can, analyze the computational complexity of optimally achieving it. In some cases, optimum solutions can be implemented in polynomial time, while in others they require NP-hard local computation. These results provide a thorough characterization of coordination and will thus aid researchers in determining the approach to take when attempting to achieve fault-tolerant coordination.