Cloud data lakes provide a modern solution for managing large volumes of data. The fundamental principle behind these systems is the separation of compute and storage layers. In this architecture, inexpensive cloud storage is utilized for data storage, while compute engines are employed to perform analytics on this data in an “on-demand” mode. However, to execute any calculations on the data, it must be transferred from the storage layer to the compute layer over the network for each query. This transfer can negatively impact calculation performance and requires significant network bandwidth. In our work, we examine various strategies to enhance query performance within a cloud data lake architecture. We begin by formalizing the problem and proposing a straightforward yet robust theoretical framework that clearly outlines the associated trade-offs. Central to our framework is the concept of a “query coverage set,” which is defined as the collection of files that need to be accessed from storage to fulfill a specific query. Our objective is to identify the minimal coverage set for each query and execute the query exclusively on this subset of files. This approach enables us to significantly improve query performance across three different domains: indexing, caching, and genetic data.

The passage of vehicles through road networks is an increasing challenge due to population density and urban centers worldwide. Frequent road crossings and heavy traffic loads often lead to congestion and lengthy travel times. Prioritizing emergency response vehicles in traffic systems is crucial for saving lives and ensuring public safety. Several approaches are suggested for integrating priority systems for ambulances, fire trucks, police vehicles, and the like. Another aspect of prioritizing vehicles is global energy and traffic savings, such as those achieved through public transportation (e.g., buses, taxis) or platoons (e.g., autonomous trucks). The suggested approaches preserve fairness among vehicles, such that vehicles with the same priority class are prioritized based on their travel starting time on a first-come, first-served basis. The results are efficient polynomial algorithms that respect the first-come, firstserved policy within each priority class and update the schedule to prioritize emergency vehicles as needed. Additionally, we introduce a practical method for testing dynamic traffic scheduling algorithms on real-world data, utilizing image processing in conjunction with GPS data within the SUMO traffic simulation software.

The use of Low Earth orbit satellites (LEO) for communication has become a reality (e.g., SpaceX). The usage of Internet communication for communicating videos is very significant. We propose a scheme based on Scalable Video Coding (SVC) that fits multicast to users with heterogeneous resolution demands (e.g., mobile phones, computer screens, and HD televisions). The use of SVC allows a significant reduction in the total communicated information, typically a reduction of dozens of percentages. We build a hierarchy of optimal Steiner trees to communicate the video-encoded layers of the SVC. The first Steiner tree spans across all the terminals and is used to convey the first layer of the SVC, and the second spans the terminals that require more resolution than the basic resolution. The third Steiner tree spans the terminals that require even more resolution, and so forth for the following Steiner trees and SVC layers. We suggest a new algorithm for finding the Steiner trees in the hierarchy, such that they are all optimal and prefer edges not used by the Steiner trees that are used for previous layers. Thus, communication can be distributed without sacrificing optimality.

Known Visual Encryption Scheme (VES) schemes encode the secret image pixels into n subpixel maps (shares) of size $m \times m$, where m is a parameter of the scheme. The pixel encoding is based on some pixel visual property, for example transparency. The resulting pixel maps contain black and white pixels and look like random collection of black and white pixels, such that it is impossible to reconstruct the original pixel. To reconstruct the original secret image, at least k out of n shares must be stacked together, where k is the scheme parameter. The reconstructed image appears grey, with varying shades of darker and lighter pixels. In this work, we introduce an optical VES solution that utilizes a physical model of wave interference. The image reconstructed using the proposed VES consists of pure black and white pixels, while maintaining the computational efficiency of traditional VES methods. An additional advantage of the proposed VES scheme is its enhanced security model. Besides being perfectly information-theoretic secure against honest and curious adversaries, it is also resilient against active, Byzantine adversaries. The proposed VES can be utilized in Flying Adhoc Networks, where a swarm of Unmanned Aerial Vehicles collaborates to search for a target based on a pre-assigned secret image.

Cloud data lakes are a modern approach to handling large volumes of data. They separate the compute and storage layers, making them highly scalable and cost-effective. However, query performance in cloud data lakes could be faster, and various efforts have been made to enhance it in recent years. We introduce our approach to this problem, which is based on a novel caching technique where instead of caching actual data, we cache metadata called a coverage set.

Cloud data lakes emerge as an inexpensive solution for storing very large amounts of data. The main idea is the separation of compute and storage layers. Thus, cheap cloud storage is used for storing the data, while compute engines are used for running analytics on this data in “on-demand” mode. However, to perform any computation on the data in this architecture, the data should be moved from the storage layer to the compute layer over the network for each calculation. Obviously, that hurts calculation performance and requires huge network bandwidth. In this paper, we study different approaches to improve query performance in a data lake architecture. We define an optimization problem that can provably speed up data lake queries. We prove that the problem is NP-hard and suggest heuristic approaches. Then, we demonstrate through the experiments that our approach is feasible and efficient (up to ×30 query execution time improvement based on the TPC-H benchmark).

We present a new framework for asynchronous permissioned blockchain with high performance and post-quantum security. The framework contains two quantum-secure asynchronous Byzantine fault tolerance (aBFT) protocols, SodsBC and SodsBC++. We leverage concurrent preprocessing to accelerate the preparation of three cryptographic objects for the repeated consensus procedure, including common random coins as the needed randomness, secret shares of symmetric encryption keys for censorship resilience, and nested hash values for external validation predicates. The key idea behind our design is that the concurrent preprocessing mechanism can be well-supported by the consensus process of blockchains. The consumed objects in a block have been generated and globally agreed upon in a previous block. All our preprocessed objects utilize proven or commonly believed to be post-quantum cryptographic tools to resist an adversary equipped with quantum computation capabilities. We evaluate our protocols and their competitors in AWS in a typical setting where, the number of participants is 100 and each block part has 20,000 transactions. The results show that SodsBC and SodsBC++ reduce the latency of two state-of-the-art but quantum-sensitive competitors Honeybadger and Dumbo by 53% and 6%, respectively.

In recent years there is huge influx of genomic data and a growing need for its analysis, yet existing genomic databases do not allow easy accessibility. We developed a pipeline that continuously pre-processes raw human genetic data. The data is then stored in a cloud data lake and can be accessed via a simple and intuitive web service and API.

Abstract We study the problem of privately emulating shared memory in message-passing networks. The system includes clients that store and retrieve replicated information on N servers, out of which e are data-corrupting malicious . When a client accesses a data-corrupting malicious server, the data field of that server response might be different from the value it originally stored. However, all other control variables in the server reply and protocol actions are according to the server algorithm. For the coded atomic storage algorithms by Cadambe et al., we present an enhancement that ensures no information leakage and data-corrupting malicious fault-tolerance. We also consider recovery after the occurrence of transient faults that violate the assumptions according to which the system was designed to operate. After their last occurrence, transient faults leave the system in an arbitrary state (while the program code stays intact). We present a self-stabilizing algorithm, which recovers after the occurrence of transient faults. This addition to Cadambe et al. considers asynchronous settings as long as no transient faults occur. The recovery from transient faults that bring the system counters (close) to their maximal values may include the use of a global reset procedure, which requires the system run to be controlled by a fair scheduler. After the recovery period, the safety properties are provided for asynchronous system runs that are not necessarily controlled by fair schedulers. Since the recovery period is bounded and the occurrence of transient faults is extremely rare, we call this design criteria self-stabilization in the presence of seldom fairness. Our self-stabilizing algorithm uses a bounded amount of storage during asynchronous executions (that are not necessarily controlled by fair schedulers). To the best of our knowledge, we are the first to address privacy, data-corrupting malicious behavior, and self-stabilization in the context of emulating atomic shared memory in message-passing systems.

Summary In this article, we consider the case in which a swarm of robots collaborates in a mission, where a few of the robots behave maliciously. These malicious Byzantine robots may be temporally or constantly controlled by an adversary. The scope is synchronized full information robot operations, where a robot that does not follow the program/policy of the swarm is immediately identified and can be remembered as Byzantine. As robots may be suspected of being Byzantine due to benign temporal malfunctions, it is imperative to forgive and forget, otherwise, a robot cannot assume collaborative actions with any other robot in the swarm. Still, remembering for a while may facilitate a policy of surrounding, isolating and freezing the movement of the misbehaving robots, by several robots, allowing the rest to perform the swarm task with no intervention. We demonstrate the need to periodically forgive and forget to realize swarm several tasks including patrolling/cleaning in the presence of possible Byzantine robots. The policy for achieving the task consists of blocking the movement of the Byzantine robot(s) by some of the robots, while the rest patrol/clean the plane.

This paper demonstrates and proves that the coordination of actions in a distributed swarm can be enhanced by using quantum entanglement. In particular, we focus on• Global and local simultaneous random walks, using entangled qubits that collapse into the same (or opposite) direction, either random direction or totally controlled simultaneous movements.• Identifying eavesdropping from malicious eavesdroppers aimed at disturbing the simultaneous random walks by using entangled qubits that were sent at random or with predefined bases.

Collaborative secure image matching is a problem that is applicable in various domains, for both – data in rest and data in motion. The problem is defined as follows. There is a secret image, and a set of n mobile agents. The set of mobile agents should match (compare) an observed image to the original secret image. In this paper we discuss some of the existing approaches, and present an alternative solution applied and analyzed for different applications. The first application is a swarm of Unmanned Aerial Vehicles (UAV) that search for a target specified by an image. The second application is a social network that serves as a smart storage device capable of performing distributed, secret image matching operations. Our solution is based on the well-known Visual Encryption Scheme (VES) and projections of visual bit maps rather than (quadratic complexity) messages exchange in implementing Secure Multi Party Computation (MPC) scheme. We present a perfect-information-theoretic secure solution for this problem. To keep the original image secrecy, at least k out of n mobile agents are required to retrieve any information about the original image.

A new CRT-based positive (non-zero) secret-sharing scheme with perfect information-theoretic (PIT) security and multiplicative homomorphism is presented. The scheme is designed to support the evaluation of multiplications of non-zero secrets of multiplicative groups.Our CRT-based scheme is partially homomorphic, supporting homomorphic multiplications. Nevertheless, it has the potential to be regarded as fully homomorphic for practical scenarios, such as bounded-sized multi-cloud databases.

In recent years, an increasing amount of data is collected in different and often, not cooperative, databases. The problem of privacy-preserving, distributed calculations over separate databases and, a relative to it, the issue of private data release was intensively investigated. However, despite a considerable progress, computational complexity and consequently, the performance of the computations, due to an increasing size of data, remains a limiting factor in real-world deployments. Especially in the case of privacy-preserving computations. In this paper, we suggest sampling as a method of improving computational performance. Sampling was a topic of extensive research in the past that recently received a boost of interest. We provide a sampling method targeted at separate, non-collaborating, vertically partitioned datasets. The method is exemplified and tested on an approximation of intersection set both with and without a privacy-preserving mechanism. An analysis of the bound on the error as a function of the sample size is discussed and a heuristic algorithm is suggested to further improve the performance. The algorithms were implemented and experimental results confirm the validity of the approach.

Identifying traffic platoons and managing vehicles on the road effectively is a challenging task that is currently investigated both in academia and industry. The challenges include the need for fast real-time gathering of relevant information, such as vehicle's location, moving direction, and speed, and instructing the vehicles in real-time to respect traffic policies according to the gathered information. In this work we present new algorithms to define platoons that are updated dynamically on the fly, allowing much better control over the traffic to gain efficiency. A platoon representative vehicle is chosen and the set of vehicles in the platoon is identified based on inductive distance criteria, that are continuously checked and considering the road graph topology and, updating the platoon memberships. In this paper, we present the main algorithms to identify and control the platoon and demonstrate this detection using a vehicle simulator.

We suggest using Fully Homomorphic Encryption (FHE) to be used, not only to keep the privacy of information but also, to verify computations with no additional significant overhead, using only part of the variables length for verification. This method supports the addition of encrypted values as well as multiplication of encrypted values by the addition of their logarithmic representations and is based on a separation between hardware functionalities. The computer/server performs blackbox additions and is based on the separation of server/device/hardware, such as the enclave, that may deal with additions of logarithmic values and exponentiation. The main idea is to restrict the computer operations and to use part of the variable for computation verification (computation fingerprints) and the other for the actual calculation. The verification part holds the FHE value, of which the calculated result is known (either due to computing locally once or from previously verified computations) and will be checked against the returned FHE value. We prove that a server with bit computation granularity can return consistent encrypted wrong results even when the public key is not provided. For the case of computer word granularity the verification and the actual calculation parts are separated, the verification part (the consecutive bits from the LSB to the MSB of the variables) is fixed across all input vectors. We also consider the case of Single Instruction Multiple Data (SIMD) where the computation fingerprints index in the input vectors is fixed across all vectors.

Cloud data lakes are a modern approach for storing large amounts of data in a convenient and inexpensive way. The main idea is the separation of compute and storage layers. However, to perform analytics on the data in this architecture, the data should be moved from the storage layer to the compute layer over the network for each calculation. Obviously, that hurts calculation performance and requires huge network bandwidth. We are exploring different approaches for adding indexing to the cloud data lakes with the goal of reducing the amounts of data read from the storage, and as a result, improving query execution time.

Data outsourcing allows data owners to keep their data at untrusted clouds that do not ensure the privacy of data and/or computations. One useful framework for fault-tolerant data processing in a distributed fashion is MapReduce, which was developed for trusted private clouds. This paper presents algorithms for data outsourcing based on Shamir's secret-sharing scheme and for executing privacy-preserving SQL queries such as count, selection including range selection, projection, and join while using MapReduce as an underlying programming model. Our proposed algorithms prevent an adversary from knowing the database or the query while also preventing output-size and access-pattern attacks. Interestingly, our algorithms do not involve the database owner, which only creates and distributes secret-shares once, in answering any query, and hence, the database owner also cannot learn the query. Logically and experimentally, we evaluate the efficiency of the algorithms on the following parameters: (i) the number of communication rounds (between a user and a server), (ii) the total amount of bit flow (between a user and a server), and (iii) the computational load at the user and the server.

SodsMPC is a quantum-safe smart contract system. SodsMPC permissioned servers (verification nodes) execute contracts by secure multi-party computation (MPC) protocols. MPC ensures the contract execution correctness while trivially keeping the data privacy. Moreover, SodsMPC accomplishes the contract business logic privacy while protecting the contract user anonymous identity simultaneously. We express the logic of a contract by a finite state machine (FSM). A state transition of the FSM is represented by a blind polynomial with secret-shared coefficients. When using MPC to compute this blind polynomial, the contract business logic privacy is obtained. These coefficients which control the logic are binary secret shares. We also propose a base conversion method among binary and integer secret shares by MPC. Our contract anonymity comes from the “mixing-then-contract” paradigm. The online phase of the SodsMPC mixing is a multiplication between a preprocessed permutation matrix and an input vector in the form of secret sharing, which accomplishes a fully randomized shuffle of the inputs and keeps the secret share form for the following contract execution. All SodsMPC components, including a verifiable secret sharing scheme, are quantum-safe, asynchronous, coping with t <; n/3 compromised servers, and robust (tolerates Byzantine servers) in both preprocessing and online phases.

The amount of data grows rapidly with time and shows no signs of stopping. Ubiquitous computing continues to collect and generate more and more data as both the number of devices grows and the capabilities of devices increase. We suggest processing the data on end devices by building a representative model of the data (“similitude” model). Sharing a smaller model instead of the entire data allows for saving computing power, network time, processing time and also, keeping the collected data private. In the past research, we suggested the use of similitude models, as compact models of data representation instead of the data itself. In this paper, we suggest the use of deep neural networks (DNN) as a data model to answer different types of queries. More specifically, we show that by building two models (generative network and auto-encoder) it is possible to answer approximately both statistical queries and membership queries without exposing the entire dataset.

The committee decided to award the 2019 Edsger W. Dijkstra Prize in Distributed Computing to Alessandro Panconesi and Aravind Srinivasan for their paper Randomized Distributed Edge Coloring via an Extension of the Chernoff-Hoeffding Bounds, SIAM Journal on Computing, volume 26, number 2, 1997, pages 350-368. A preliminary version of this paper appeared as Fast Randomized Algorithms for Distributed Edge Coloring, Proceedings of the Eleventh Annual ACM Symposium Principles of Distributed Computing (PODC), 1992, pages 251-262.

We introduce the AdaptiveClimb cache policy, a new policy for cache management. This policy improves LRU to gain higher performance in a fixed probability scenario, without maintaining statistics for each item. Rather, it stores a single value (the current jump), while preserving the fast adaptation of probability changes of LRU. AdaptiveClimb is a modification of CLIMB cache policy, that unlike CLIMB changes the number of positions shifts according to whether the last request has been a hit or a miss. Performance of CLIMB is close to that of the optimal off-line algorithm, but its stabilization time is long. LRU is much more sensitive to changes, but it is sensitive to noise. Thus, AdaptiveClimb combines these two advantages in a single algorithm with both good performance and short stabilization time.

In this paper, we define a new concept neighborhood mutual remainder (NMR). An NMR distributed algorithms should satisfy global fairness, l-exclusion and repeated local rendezvous requirements. We give a simple self-stabilizing algorithm to demonstrate the design paradigm to achieve NMR, and also present applications of NMR to a Look-Compute-Move robot system.

Hadoop and Spark are widely used distributed processing frameworks for large-scale data processing in an efficient and fault-tolerant manner on private or public clouds. These big-data processing systems are extensively used by many industries, e.g., Google, Facebook, and Amazon, for solving a large class of problems, e.g., search, clustering, log analysis, different types of join operations, matrix multiplication, pattern matching, and social network analysis. However, all these popular systems have a major drawback in terms of locally distributed computations, which prevent them in implementing geographically distributed data processing. The increasing amount of geographically distributed massive data is pushing industries and academia to rethink the current big-data processing systems. The novel frameworks, which will be beyond state-of-the-art architectures and technologies involved in the current system, are expected to process geographically distributed data at their locations without moving entire raw datasets to a single location. In this paper, we investigate and discuss challenges and requirements in designing geographically distributed data processing frameworks and protocols. We classify and study batch processing (MapReduce-based systems), stream processing (Spark-based systems), and SQL-style processing geo-distributed frameworks, models, and algorithms with their overhead issues.

In recent years, an increasing amount of data is collected in different and often, not cooperative, databases. The problem of privacy-preserving, distributed calculations over separate databases and, a relative to it, the issue of private data release were intensively investigated. However, despite a considerable progress, computational complexity, due to an increasing size of data, remains a limiting factor in real-world deployments, especially in case of privacy-preserving computations. In this paper, we suggest sampling as a method of improving computational performance. Sampling was a topic of extensive research that recently received a boost of interest. We provide a sampling method targeted at separate, non-collaborating, vertically partitioned datasets. The method is exemplified and tested on approximation of intersection set both without and with privacy-preserving mechanism. An analysis of the bound on error as a function of the sample size is discussed and heuristic algorithm is suggested to further improve the performance. The algorithms were implemented and experimental results confirm the validity of the approach.

Blockchain's ever increasing size has become a major problem. Bitcoin [7], for example, has grown to 115120 MB as of May 2017, which is roughly 115 GB. This uncontrollable growth of the Blockchain is bound to become an issue in the future, as hard disks may become too small to store the entire Blockchain history and traversing the transactions databases may become increasingly slow. Already, there are lightweight clients in various Blockchain platforms (Bitcoin included), who do not store the entire chain locally but rely on a third party to send them the blocks they need. There are many issues with these clients, mainly security problems, since they go back to trusting a central authority rather than gaining trust from several distributed peers. These clients' knowledge of the Blockchain is solely based on some third party that should be trusted, while the conceptual base for Blockchain is trust distributing. In this paper we present two Blockchain abbreviation schemes. The first one is based on the Ethereum [8] project and proposes replacing the full Blockchain with a new Genesis block, which summarizes everyone's account balances at a certain point in time. One possible benefit is to use less communication while still storing the prefix of the old Blockchain (or signature of the Blockchain that can validate a version archived by other participants) in a local archive. Here we trade loss of transaction history for efficiency. Our second contribution is a UNIX based architecture using the file system, for implementing Blockchain. We demonstrate a Blockchain abbreviation technique for this architecture too.

We study the problem of seamlessly updating several routes in a network, in the context of Software-Defined Networking (SDN). A set of routes pairs (Ci, Ni) is given, where each new Nishould replace the existing Ci. We look for a way of gradual updating, so that routing cycles are never created during the replacement process. In that, we follow the recent paper of Delaet et al., which considered the case of updating a single route. In addition, we require avoiding congestion on links. We provide an example of several routes replacement, where the strategy suggested by Delaet et al. fails: it arrives at a deadlock, while a legal way of replacement exists. We suggest a dependence graph model for solving the problem. The dependence graph nodes are: a) the sub-routes resulting from sub-dividing all Niand Ciby the routers common to Niand Ci, and b) the potentially congested links. We define which new sub-routes are legal for replacement. Further, we describe the changes in routing and in the dependence graph resulting from launching a legal new subroute. Summarizing, we reduce the route replacement problem to finding an (optimal) sequence of launchings of currently legal new sub-routes, using the dynamic dependence graph. Moreover, we suggest a novel meta-approach for resolving deadlocks, by utilizing the optical wires that connect the SDN controller to the routers.

In this paper, we examine the possibility to utilize the well-known approximations of Jaccard metric in order to reduce computational complexity of Edit Distance metric estimation. The scope of our analytical results is the representing strings rather than the original (raw) textual data, still in practice we obtained a solid indication that the results can be applied to (raw) strings that have low n-gram repetitions. We formulate inequalities between the Jaccard metric and the Edit Distance, that impose upper and lower bounds on the Edit Distance values in terms of the Jaccard values. We validate our inequality over strings of API call traces where (the small) clusters obtained are refined by applying Edit Distance. Jaccard is a measure of similarity between two sets, while Edit Distance is a measure for two strings, such as traces of API calls. The computation associated with creating n-grams and using Jaccard similarity is much more efficient than the computation of Edit Distance (linear versus quadratic time complexity). Thus, our new bounds on the Edit Distance given the Jaccard value are of practical interest. Another new aspect we coped with in our research is the inherent imbalance between malicious and benign API traces that are harvested from the system, as most of the traces are benign. We performed clustering only on the malware traces where each cluster concentrates malware with some specific common essence. The obtained clustering is used with great success in classifying new query traces for being either benign or malware. The traces for our research were obtained from the KVM hypervisor Runtime Execution Introspection and Profiling (REIP) system based on Virtual Machine Introspection (VMI) techniques to profile hooked Windows API calls.

Formal verification serves as the theoretical basis for the engineering task of correctness and performance (quality) assurance. State of the art model checking, automatic specification refinement and theorem proving are employed to tackle the often undecidable (as imposed by the halting problem) task of complete verification. In this paper we formalize, prove and demonstrate a new unobtrusive way to test a system during runtime. Invocation of actions and examination of reaction of the system and components of the system are examined in run time in an holistic abstract manner, namely, the current state (e.g., state snapshot) the executable (e.g., program) and the environmental current condition (e.g., operating system, hypervisor) are examined by invoking actions and examining the reactions without influencing the actual execution semantics.

Self-stabilization refers to the ability of systems to recover after temporal violations of conditions required for their correct operation. Such violations may lead the system to an arbitrary state from which it should automatically recover. Today, beyond recovering functionality, there is a need to recover security and confidentiality guarantees as well. To the best of our knowledge, there are currently no self-stabilizing protocols that also ensure recovering confidentiality, authenticity, and integrity properties. Specifically, self-stabilizing systems are designed to regain functionality which is, roughly speaking, desired input output relation, ignoring the security and confidentiality of computation and its state. Distributed (cryptographic) protocols for generic secure and privacy-preserving computation, e.g., secure Multi-Party Computation (MPC), usually ensure secrecy of inputs and outputs, and correctness of computation when the adversary is limited to compromise only a fraction of the components in the system, e.g., the computation is secure only in the presence of an honest majority of involved parties. While there are MPC protocols that are secure against a dishonest majority, in reality, the adversary may compromise all components of the system for a while; some of the corrupted components may then recover, e.g., due to security patches and software updates, or periodical code refresh and local state consistency check and enforcement based on self-stabilizing hardware and software techniques. It is currently unclear if a system and its state can be designed to always fully recover following such individual asynchronous recoveries. This paper introduces Secure Self-stabilizing Computation which answers this question in the affirmative. Secure self-stabilizing computation design ensures that secrecy of inputs and outputs, and correctness of the computation are automatically regained, even if at some point the entire system is compromised. We consider the distributed computation task as the implementation of virtual global finite satiate machine (FSM) to present commonly realized computation. The FSM is designed to regain consistency and security in the presence of a minority of Byzantine participants, e.g., one third of the parties, and following a temporary corruption of the entire system. We use this task and settings to demonstrate the definition of secure self-stabilizing computation. We show how our algorithms and system autonomously restore security and confidentiality of the computation of the FSM once the required corruption thresholds are again respected.

Controversially, more data is not necessary better than less data. The explosion of the data lead to a number of interesting practical and theoretical problems. Among those problems are the need to filter, process, verify, index, distribute, protect and make redundant copies of the data. This data “massaging” usually take a lot of time and processing power. However, the quantity of the collected data does not necessary mean quality, as a lot of data is repetitive or does not contain any new information. Nevertheless, it still has to be processed, filtered, consumes high communication volume, has to be protected from breaches and from storage failures. In this position paper we propose to perform data reduction techniques on the collected (big) data prior to gathering of the data in a single location. In many cases (exemplified by two use-cases), especially in Internet-of-Things (IoT), those techniques might save tremendous amounts of power, processing time and network traffic.

We propose a peripheral authentication scheme for autonomous vehicles. A mutual authentication protocol is required to secure every peripheral device access to a vehicle. Specifically, we present a vehicle to peripheral device authentication scheme. In addition, our three way handshake scheme for vehicle to keyfob authentication scheme based on generalized peripheral authentication scheme has been proposed. The vehicle to keyfob authentication scheme is adapted and improved with an additional attribute verification of the keyfob holder. Conventionally, vehicle to keyfob authentication is realized through a challenge-response verification protocol. An authentic coupling between the vehicle identity and the keyfob avoids any illegal access to the vehicle. However, these authentication messages can be relayed by an active adversary, thereby, can amplify the actual distance between the authentic vehicle and the keyfob. Eventually, through this malicious relaying an adversary can possibly get access to the vehicle, without any effort to generate or decode the crypto credentials. Our solution is a two party, three way handshake scheme with proactive and reactive commitment verification. Conceptually, our solution is different than the distance bounding protocols that requires multiple rounds of round trip delay measurement.

In a secret sharing scheme a dealer shares a secret s among n parties such that an adversary corrupting up to t parties does not learn s, while any t+1 parties can efficiently recover s. Over a long period of time all parties may be corrupted thus violating the threshold, which is accounted for in Proactive Secret Sharing (PSS). PSS schemes periodically rerandomize (refresh) the shares of the secret and invalidate old ones. PSS retains confidentiality even when all parties are corrupted over the lifetime of the secret, but no more than t during a certain window of time, called the refresh period. Existing PSS schemes only guarantee secrecy in the presence of an honest majority with less than n2 total corruptions during a refresh period; an adversary corrupting a single additional party, even if only passively, obtains the secret. This work is the first feasibility result demonstrating PSS tolerating a dishonest majority, it introduces the first PSS scheme secure against t<n passive adversaries without recovery of lost shares, it can also recover from honest faulty parties losing their shares, and when tolerating e faults the scheme tolerates t<n-e passive corruptions. A non-robust version of the scheme can tolerate t

A MapReduce algorithm can be described by a mapping schema , which assigns inputs to a set of reducers, such that for each required output there exists a reducer that receives all the inputs participating in the computation of this output. Reducers have a capacity that limits the sets of inputs they can be assigned. However, individual inputs may vary in terms of size. We consider, for the first time, mapping schemas where input sizes are part of the considerations and restrictions. One of the significant parameters to optimize in any MapReduce job is communication cost between the map and reduce phases. The communication cost can be optimized by minimizing the number of copies of inputs sent to the reducers. The communication cost is closely related to the number of reducers of constrained capacity that are used to accommodate appropriately the inputs, so that the requirement of how the inputs must meet in a reducer is satisfied. In this work, we consider a family of problems where it is required that each input meets with each other input in at least one reducer. We also consider a slightly different family of problems in which each input of a list, X , is required to meet each input of another list, Y , in at least one reducer. We prove that finding an optimal mapping schema for these families of problems is NP-hard, and present a bin-packing-based approximation algorithm for finding a near optimal mapping schema.

Software-Defined Networking (SDN) decouples the control and data planes, enabling limitless possibilities for implementing services and applications on top of the network abstraction layer. The centralized controller provides a real-time view of the entire underlying network infrastructure and therefore, management of the agile network becomes more simplified. This flexibility requires online routing updates, but during these updates, consistency has to be preserved, i.e., No packet losses or unrecognized duplications should occur. Moreover, routing updates should be done on the fly in an application-seamless fashion. Where no significant irregular delays or "communication hiccups" in packet arrivals are introduced due to the (frequent) updates. In this paper we present the first seamless consistency during on-the-fly routing updates, allowing the sender to send packets in an unchanged rate during the entire process, rate that is identical to the rate prior and after the update. The main idea is to use multicast on portions of the route, i.e., To send a packet both in the old and the new routes and only when the controller verifies the establishment and operation of the specific portion of the new route, it can remove the corresponding portion from the old route.

Modern vehicles are configured to exchange warning messages through IEEE 1609 Dedicated Short Range Communication (DSRC) over IEEE 802.11p Wireless Access in Vehicular Environment (WAVE). Essentially, these warning messages must associate an authentication factor such that the verifier authenticates the message origin via visual binding. Interestingly, the existing vehicle communication incorporates the message forward-ability as a requested feature for numerous applications. On the contrary, the vehicle security infrastructure is vulnerable to message forwarding i.e., Messages seem to originate from a malicious vehicle (due to non-detectable message relaying) instead of the actual message sender. We introduce the non forward-able authentication to avoid an adversary coalition attack scenario. These messages should be identifiable with respect to the immediate sender at every hop. We propose to utilize immediate optical response verification in association with the authenticated key exchange over radio channel. These optical responses are generated through hardware means, i.e., A certified Physically Unclonable Function (PUF) device embedded on the front and rear of the vehicle.

A stabilizing Byzantine single-writer single-reader (SWSR) regular register, which stabilizes after the first invoked write operation, is first presented. Then, new/old ordering inversions are eliminated by the use of a (bounded) sequence number for writes, obtaining a practically stabilizing SWSR atomic register. A practically stabilizing Byzantine single-writer multi-reader (SWMR) atomic register is then obtained by using several copies of SWSR atomic registers. Finally, bounded time-stamps, with a time-stamp per writer, together with SWMR atomic registers, are used to construct a practically stabilizing Byzantine multi-writer multi-reader (MWMR) atomic register. In a system of n servers implementing an atomic register, and in addition to transient failures, the constructions tolerate t<n/8 Byzantine servers if communication is asynchronous, and t

We study the problem of privately emulating shared memory in message passing networks. The system includes $N$ servers, and at most e semi-Byzantine servers that can deviate from the algorithm by sending corrupted data. Moreover, at most f servers can fail and stop.

We analyze the effect of network topology on the pattern stability of the Hopfield neural network in the case of general graphs. The patterns are randomly selected from a uniform distribution. We start the Hopfield procedure from some pattern v. An error in an entry e of v is the situation where, if the procedure is started at e, the value of e flips. Such an entry is an instability point. Note that we disregard the value at e by the end of the procedure, as well as what happens if we start the procedure from another pattern v' or another entry e' of v. We measure the instability of the system by the expected total number of instability points of all the patterns. Our main result is that the instability of the system does not depend on the exact topology of the underlying graph, but rather only on its degree sequence. Moreover, for a large number of nodes, the instability can be approximated by mΣni=1(1 − Φ(√δi/m−1)), where is the standard normal distribution function and δ1, . . . , δn are the degrees of the nodes.

Private interconnection between datacenters is an essential goal due to the popularity of IaaS (Infrastructure as a Service) and SaaS (Software as a Service) architectures. Datacenters intercommunication is needed when an enterprise want to stretch its data center capacity by extending it with another data center on the cloud. This interconnection has to be private so this stretch will be considered only virtual. Our research focuses on achieving that privacy on top of SDN-based network. This privacy is achieved without the need to use keys. Namely, information theoretic secure rather than only computational secure. The general idea is to use SDN to enable the creation of several tunnels between each pair of datacenters that intercommunicate. The source uses secret sharing technique to encrypt its data and create n shares. In order to reconstruct the data, the destination needs to have at least k shares out of the n shares that were sent by the sender. We design an algorithm that creates these tunnels with the constraint that only less than k shares of the same information can reach a single router. This way we achieve a private and secure interconnection between the datacenters.

Self-Organization is based on adaptivity. Adaptivity should start with the very basic fundamental communication tasks such as encoding the information to be transmitted or stored. Obviously, the less signal transmitted the less energy in transmission used. In this paper we present a novel on-line and entropy adaptive compression scheme for streaming unbounded length inputs. The scheme extends the window dictionary Lempel-Ziv compression, is adaptive and is tailored to on-line compress inputs with non stationary entropy. Specifically, the window dictionary size is changed in an adaptive manner to fit the current best compression rate for the input. On-line Entropy Adaptive Compression scheme (EAC), that is introduced and analyzed in this paper, examines all possible sliding window sizes over the next input portion to choose the optimal window size for this portion, a size that implies the best compression ratio. The size found is then used in the actual compression of this portion. We suggest an adaptive encoding scheme, which optimizes the parameters block by block, and base the compression performance on the optimality proof of Lempel Ziv algorithm when applied to blocks. The EAC scheme was tested over files of different types (docx, ppt, jpeg, xls) and over synthesized files that were generated as segments of homogeneous Markov Chains. Our experiments demonstrate that the EAC scheme typically provides a higher compression ratio than LZ77 does, when examined in the scope of on-line per-block compression of transmitted (or compressed) files.

In the near future, vehicles will establish a spontaneous connection over a wireless radio channel, coordinating actions and information. Security infrastructure is most important in such a hazardous scope of vehicles communication for coordinating actions and avoiding accidents on the roads. One of the first security issues that need to be established is authentication. Vehicle authentication with visual binding prior to establishing a wireless radio channel of communication is useful only when the vehicles possess unique visual attributes. These vehicle static attributes (e.g., Licence number, brand and color) are certified together with the vehicle public key. Therefore, we consider the case of multiple malicious vehicles with identical visual static attributes. Apparently, dynamic attributes (e.g., Location and direction) can uniquely define a vehicle and can be utilized to resolve the true identity of vehicles. However, unlike static attributes, dynamic attributes cannot be signed by a trusted authority beforehand. We propose an approach to verify the coupling between non-certified dynamic attributes and certified static attributes on an auxiliary communication channel, for example, a modulated laser beam. Furthermore, we illustrate that the proposed approach can be used to facilitate the usage of existing authentication protocols such as NAXOS, in the new scope of ad-hoc vehicle networks.

This paper presents the architecture for a self-stabilizing hypervisor able to recover itself in the presence of Byzantine faults regardless of the state it is currently in. Our architecture is applicable to wide variety of underlying hardware and software and does not require augmenting computers with special hardware. The actions representing defense and recovery strategies can be specified by a user. We describe our architecture in OS-independent terms, thus making it applicable to various virtualization infrastructures. We also provide a prototype extending the Linux-based hypervisor KVM with the self-stabilizing functionality. These features allow augmenting KVM with robustness functionality in the coming stages and moving to cloud management system architectures such as OpenStack to support more industrial scenarios.

The term programmable matter refers to matter which has the ability to change its physical properties (shape, density, moduli, conductivity, optical properties, etc.) in a programmable fashion, based upon user input or autonomous sensing. This has many applications like smart materials, autonomous monitoring and repair, and minimal invasive surgery, so there is a high relevance of this topic to industry and society in general. While programmable matter has just been science fiction more than two decades ago, a large amount of research activities can now be seen in this field in the recent years. Often programmable matter is envisioned, as a very large number of small locally interacting computational \emph{particles}. We propose the Amoebot model, a new model which builds upon this vision of programmable matter. Inspired by the behavior of amoeba, the Amoebot model offers a versatile framework to model self-organizing particles and facilitates rigorous algorithmic research in the area of programmable matter.

We consider the problem of clock synchronization in a wireless setting where processors must minimize the number of times their radios are used to save energy. Energy efficiency is a central goal in wireless networks, especially if energy resources are severely limited, as occurs in sensor and ad hoc networks, and in many other settings. The problem of clock synchronization is fundamental and intensively studied in the field of distributed algorithms. In the current setting, the problem is to synchronize clocks of m processors that wake up in arbitrary time points, such that the maximum difference between wake-up times is bounded by a positive integer n . (Time intervals are appropriately discretized to allow communication of all processors that are awake in the same discrete time unit.) Currently, the best-known results for synchronization for single-hop networks of m processors is a randomized algorithm due to Bradonjic et al. [2009] of O (√ n / m ⋅ poly - log ( n )) radio use times per processor, and a lower bound of Ω (√ n / m ). The main open question left in their work is to close the poly-log gap between the upper and the lower bound, and to derandomize their probabilistic construction and eliminate error probability. This is exactly what we do in this article. That is, we show a deterministic algorithm with radio use of Θ (√ n / m ), which exactly matches the lower bound proven in Bradonjic et al. [2009] to a small multiplicative constant. Therefore, our algorithm is optimal in terms of energy efficiency and completely resolves a long sequence of works in this area [Bradonjic et al. 2009; Moscribroda et al. 2006; McGlynn and Borbash 2001; Polastre et al. 2004]. Moreover, our algorithm is optimal in terms of running time as well. To achieve these results, we devise a novel adaptive technique that determines the times when devices power their radios on and off. This technique may be of independent interest. In addition, we prove several lower bounds on the energy efficiency of algorithms for multihop networks. Specifically, we show that any algorithm for multihop networks must have radio use of Ω (√ n ) per processor. Our lower bounds hold even for specific kinds of networks, such as networks modeled by unit disk graphs and highly connected graphs. Our results imply that the simple deterministic algorithm devised for two-processor networks in Bradonjic et al. [2009] with efficiency O (√ n ) can be used in multihop networks, and it is the most efficient solution in terms of energy use.

In this paper, we present a new family of fountain codes which overcome adversarial errors. That is, we consider the possibility that some portion of the arriving packets of a rateless erasure code are corrupted in an undetectable fashion. In practice, the corrupted packets may be attributed to a portion of the communication paths which are controlled by an adversary or to a portion of the sources that are malicious. The presented codes resemble and extend rateless codes. Yet, their benefits over existing coding schemes are manifold. First, to overcome the corrupted packets, our codes use information theoretic techniques, rather than cryptographic primitives. Thus, no secret channel between the senders and the receivers is required. Second, the encoders in the suggested scheme are oblivious to the strength of the adversary, yet perform as if its strength was known in advance. Third, the sparse structure of the codes facilitates efficient decoding. Finally, the codes easily fit a decentralized scenario with several sources, when no communication between the sources is allowed. We present both exhaustive as well as efficient decoding rules. Beyond the obvious use as a rateless codes, our codes have important applications in distributed computing.

In this paper, we consider a set of n mobile wireless nodes, which have no information about each other. The only information a single node holds is its current location and future mobility plan. We develop a two-phase distributed self-stabilizing scheme for producing a bounded hop-diameter communication graph. In the first phase, nodes construct a temporary underlying topology and disseminate their current location and mobility plans. This is followed by a second phase, in which nodes construct the desired topology under two modes: static and dynamic. The static mode provides a fixed topology which does not change in spite of node movements; the dynamic mode allows the topology to change; however, the hop-diameter remains the same. We provide an O(λ,λ2)-bicriteria approximation (in terms of total energy consumption and network lifetime, respectively) algorithm in the static mode: for an input parameter λ, we construct a static h-bounded hop communication graph, where h=n/λ + log λ. In the dynamic mode, given a parameter h, we construct an optimal (in terms of network lifetime) h-bounded hop communication graph when every node moves with constant speed in a single direction along a straight line during each time interval. Our results are validated through extensive simulations.

We present schemes for providing anonymous transactions while privacy and anonymity are preserved, providing user's anonymous authentication in distributed networks such as the Internet. We first present a practical scheme for anonymous transactions while the transaction resolution is assisted by a Trusted Authority. This practical scheme is extended to a theoretical scheme where a Trusted Authority is not involved in the transaction resolution. Both schemes assume that all the players interact over anonymous secure channels. Given authority that generates for each player hard to produce evidence EVID (e.g., problem instance with or without a solution) to each player, the identity of a user U is defined by the ability to prove possession of aforementioned evidence. We use zero-knowledge proof techniques to repeatedly identify U by providing a proof that U has evidence EVID , without revealing EVID , therefore avoiding identity theft. In both schemes the authority provides each user with a unique random string. A player U may produce a unique user name and password for each other player S using a one-way function over the random string and the IP address of S . The player does not have to maintain any information in order to reproduce the user name and password used for accessing a player S . Moreover, the player U may execute transactions with a group of players S U in two phases; in the first phase the player interacts with each server without revealing information concerning its identity and without possibly identifying linkability among the servers in S U . In the second phase the player allows linkability and therefore transaction commitment with all servers in S U , while preserving anonymity (for future transactions).

In this work, we suggest hardware and software components that enable the creation of a self-stabilizing os/vmm on top of an off-the-shelf, nonself-stabilizing processor. A simple "watchdog” hardware that is called a periodic reset monitor (prm) provides a basic solution. The solution is extended to stabilization enabling hardware (seh) which removes any real time requirement from the os/vmm. A stabilization enabling system that extends the seh with software components provides the user (an os/vmm designer) with a self-stabilizing processor abstraction. The method uses only a modest addition of hardware, which is external to the microprocessor. We demonstrate our approach on the XScale core by Intel. Moreover, we suggest methods for the adaptation of existing system code (e.g., code for operating systems) to be self-stabilizing. One method allows capturing and enforcing the configuration used by the program, thus reducing the work of the self-stabilizing algorithm designer to considering only the dynamic (nonconfigurational) parts of the state. Another method is suggested for ensuring that, eventually, addresses of branch commands are examined using a sanity check segment. This method is then used to ensure that a sanity check is performed before critical operations. One application of the latter method is for enforcing a full separation of components in the system.

Modern business activities rely on extensive email exchange. Various solutions attempt to analyze email exchange in order to prevent emails from being sent to the wrong recipients. However there are still no satisfying solutions; many email addressing mistakes are not detected and in many cases correct recipients are wrongly marked as potential addressing mistakes. In this paper we present a new approach for preventing emails addressing mistakes in organizations. The approach is based on analysis of emails exchange among members of the organization and the identification of groups based on common topics. Each member's topics are then used during the enforcement phase for detecting potential leakage. When a new email is composed and about to be sent, each email recipient is analyzed. A recipient is approved if the email's content belongs to at least one of the topics common to the sender and the recipient. We evaluated the new approach using the Enron Email dataset. Our evaluation results suggest that the new approach easily copes with email recipients that have no previous direct connection with the sender.

Players in a game are assumed to be totally rational and absolutely smart. However, in reality all players may act in non-rational ways and may fail to understand and find their best actions. In particular, participants in social interactions, such as lotteries and auctions, cannot be expected to always find by themselves the "best-reply" to any situation. Indeed, agents may consult with others about the possible outcome of their actions. It is then up to the counselee to assure the rationality of the consultant's advice. We present a distributed computer system infrastructure, named rationality authority, that allows safe consultation among (possibly biased) parties. The parties' advices are adapted only after verifying their feasibility and optimality by standard formal proof checkers. The rationality authority design considers computational constraints, as well as privacy and security issues, such as verification methods that do not reveal private preferences. Some of the techniques resembles zero-knowledge proofs. A non-cooperative game is presented by the game inventor along with its (possibly intractable) equilibrium. The game inventor advises playing by this equilibrium and offers a checkable proof for the equilibrium feasibility and optimality. Standard verification procedures, provided by trusted (according to their reputation) verification procedures, are used to verify the proof. Thus, the proposed rationality authority infrastructure facilitates the applications of game theory in several important real-life scenarios by the use of computing systems.

We propose efficient schemes for information-theoretically secure key exchange in the Bounded Storage Model (BSM), where the adversary is assumed to have limited storage. Our schemes generate a secret One Time Pad (OTP) shared by the sender and the receiver,from a large number of public random bits produced by the sender or by an external source. Our schemes initially generate a small number of shared secret bits, using known techniques. We introduce a new method to expand a small number of shared bits to a much longer, shared key.

Many anonymous peer-to-peer (P2P) file sharing systems have been proposed in recent years. One problem that remains open is how to protect the anonymity of all participating users, namely, reader, server and publisher. In this work we propose a novel solution for a P2P file sharing system. Our solution provides overall anonymity to all participating users.

We present information-theoretically secure schemes for sharing and modifying secrets among a dynamic swarm of computing devices. The schemes support an unlimited number of changes to the swarm including players joining and leaving the swarm, while swarms may be merged, cloned or split. The schemes securely and distributively maintain a global state for the swarm, and support an unlimited number of changes to the state according to received input. Our schemes are based on a novel construction of a strongly oblivious universal Turing Machine and on a distributed evaluation of this TM that reveals nothing to an adversary beyond a bound on the space complexity of the TM.

Betweenness-Centrality measure is often used in social and computer communication networks to estimate the potential monitoring and control capabilities a vertex may have on data flowing in the network. In this article, we define the Routing Betweenness Centrality (RBC) measure that generalizes previously well known Betweenness measures such as the Shortest Path Betweenness, Flow Betweenness, and Traffic Load Centrality by considering network flows created by arbitrary loop-free routing strategies. We present algorithms for computing RBC of all the individual vertices in the network and algorithms for computing the RBC of a given group of vertices, where the RBC of a group of vertices represents their potential to collaboratively monitor and control data flows in the network. Two types of collaborations are considered: (i) conjunctive—the group is a sequences of vertices controlling traffic where all members of the sequence process the traffic in the order defined by the sequence and (ii) disjunctive—the group is a set of vertices controlling traffic where at least one member of the set processes the traffic. The algorithms presented in this paper also take into consideration different sampling rates of network monitors, accommodate arbitrary communication patterns between the vertices (traffic matrices), and can be applied to groups consisting of vertices and/or edges. For the cases of routing strategies that depend on both the source and the target of the message, we present algorithms with time complexity of O ( n 2 m ) where n is the number of vertices in the network and m is the number of edges in the routing tree (or the routing directed acyclic graph (DAG) for the cases of multi-path routing strategies). The time complexity can be reduced by an order of n if we assume that the routing decisions depend solely on the target of the messages. Finally, we show that a preprocessing of O ( n 2 m ) time, supports computations of RBC of sequences in O ( kn ) time and computations of RBC of sets in O ( n 3 n ) time, where k in the number of vertices in the sequence or the set.

Distributed algorithm designers often assume that system processes execute the same predefined software. Alternatively, when they do not assume that, designers turn to non-cooperative games and seek an outcome that corresponds to a rough consensus when no coordination is allowed. We argue that both assumptions are inapplicable in many real distributed systems, e.g., the Internet, and propose designing self-stabilizing and Byzantine fault-tolerant distributed game authorities. Once established, the game authority can secure the execution of any complete information game. As a result, we reduce costs that are due to the processes’ freedom of choice. Namely, we reduce the price of malice.

As more and more services are provided by servers via the Internet, Denial-of-Service (DoS) attacks pose an increasing threat to the Internet community. A DoS attack overloads the target server with a large volume of adverse requests, thereby rendering the server unavailable to ¿well-behaved¿ users. Recently, the novel paradigm of traffic ownership that enables the clients of Internet service providers (ISP) to configure their own traffic processing policies has gained popularity. In this paper, we propose two algorithms belonging to this paradigm that allow attack targets to dynamically filter their incoming traffic based on a distributed policy. The proposed algorithms defend the target against DoS and distributed DoS (DDoS) attacks and simultaneously ensure that it continues to receive valuable users' traffic. In a nutshell, a target can define a filtering policy which consists of a set of traffic classification rules and the corresponding amounts of traffic, measured in bandwidth units, which match each rule. The filtering algorithm is enforced by the ISP's or the Network Service Provider's (NSP) routers when a target is being overloaded with traffic. The goal is to maximize the amount of filtered traffic forwarded to the target, according to the filtering policy, from the ISP's or the NSP's network. The first algorithm we propose relies on complete collaboration among the ISP/NSP routers. It computes the filtering policy in polynomial time and delivers the best possible traffic mix to the target. The second algorithm is a distributed algorithm which assumes no collaboration among the ISP/NSP routers, each router only uses local information about its incoming traffic. We show the intuition behind the proof of lower bound on the second algorithm's worst-case performance.

This paper suggests a new framework in which the quality of a (not necessarily optimal) heuristic solution is certified by an approximation algorithm. Namely, the result of a heuristic solution is accompanied by a scale obtained from an approximation algorithm. The creation of a scale is efficient whereas solutions obtained from an approximation algorithm usually involve long calculation when compared to a heuristic approach. On the other hand, a result obtained by heuristics without a scale might not be useful. We investigate criteria for choosing an approximation scheme for producing a scale. To obtain a scale in practice, we examine approximations not only by their asymptotic behavior, but also examine relations as a function of the input size of a given problem. We examine, as case studies only, heuristic and approximation algorithms for the SINGLE KNAPSACK, MAX 3-SAT, and MAXIMUM BOUNDED 3-DIMENSIONAL MATCHING (MB3DM) NP-hard problems. We obtain certificates for the heuristic runs by using fitting approximations. Within the scope of distributed computing one may execute two distributed Algorithms, one that is based on approximation and another on heuristics. The approximation result is used to certify the heuristic result and stop (the possibly exponential time) heuristic search. Thus, the reliability of the obtained solution can be estimated and certificated.

We introduce the use of movement-signals (analogously to flight signals and bees waggle) as a mean to transfer messages, enabling the use of distributed algorithms among the robots. We propose one-to-one deterministic movement protocols that implement explicit communication.

In this paper, we study the wireless synchronization problem which requires devices activated at different times on a congested single-hop radio network to synchronize their round numbering. We assume a collection of n synchronous devices with access to a shared band of the radio spectrum, divided into F narrowband frequencies. We assume that the communication medium suffers from unpredictable, perhaps even malicious interference, which we model by an adversary that can disrupt up to t frequencies per round. Devices begin executing in different rounds and the exact number of participants is not known in advance.

Self-stabilization is an elegant approach for designing fault tolerant systems. A system is considered self-stabilizing if, starting in any state, it converges to the desired behavior. Self-stabilizing algorithms were designed for solving fundamental distributed tasks, such as leader election, token circulation and communication network protocols. The algorithms were expressed using guarded commands or pseudo-code. The realization of these algorithms requires the existence of a (self-stabilizing) infrastructure such as a self-stabilizing microprocessor and a self-stabilizing operating system for their execution. Moreover, the high-level description of the algorithms needs to be converted into machine language of the microprocessor. In this article, we present our design for a self-stabilization preserving compiler. The compiler we designed and implemented transforms programs written in a language similar to the abstract state machine (ASM). The compiler preserves the stabilization property of the high level program.

We study the problem of secure communication in a multi-channel, single-hop radio network with a malicious adversary that can cause collisions and spoof messages. We assume no pre-shared secrets or trusted-third-party infrastructure. The main contribution of this paper is f-AME: a randomized (f)ast-(A)uthenticated (M)essage (E)xchange protocol that enables nodes to exchange messages in a reliable and authenticated manner. It runs in O(|E|t2 log n) time and has optimal resilience to disruption, where E is the set of pairs of nodes that need to swap messages, n is the total number of nodes, C the number of channels, and t < C the number of channels on which the adversary can participate in each round. We show how to use f-AME to establish a shared secret group key, which can be used to implement a secure, reliable and authenticated long-lived communication service. The resulting service requires O(nt3 log n) rounds for the setup phase, and O(t log n) rounds for an arbitrary pair to communicate. By contrast, existing solutions rely on pre-shared secrets, trusted third-party infrastructure, and/or the assumption that all interference is non-malicious.

Transactional memory (TM) is a key concurrent programming abstraction. Several software-based transactional memory (STM) implementations have been developed in recent years. All STM implementations must guarantee transaction atomicity but different STM implementations may provide different progress guarantees. In order to ensure progress, an STM implementation must resolve transaction conflicts. This is done either by the implementation itself or by delegating conflict resolution to a separate contention manager module that tries to resolve transaction collisions once they are detected.

This work presents approaches for designing the input-output device management components of self-stabilizing operating systems. As an example, we demonstrate the nonstability of the ata standard protocol for storage devices. We state the requirements that an operating system and I/O devices should satisfy in order to become self-stabilizing. Then we suggest two solutions to satisfy these requirements. The first uses leases to guarantee progress from the I/O device side. The second assumes stabilization of the I/O device, and uses snapshots to perform consistency checks. A device driver for a PC hard-disk, using the first solution, was implemented. By supplying an infrastructure for practical self-stabilizing systems, robust and dependable systems can be achieved.

This work presents several approaches for designing self-stabilizing operating systems. The first approach is based on periodical automatic reinstalling of the operating system and restart. The second reinstalls the executable portion of the operating system and uses predicates on the operating system state (content of variables) to ensure that the operating system does not diverge from its specifications. The last approach presents an example of a tailored self-stabilizing very tiny operating system. Prototypes using the Intel Pentium processor were composed.

This position paper advocates the use of the well defined and provable self-stabilization property of a system, to achieve the goals of the self-* paradigms and autonomic computing. Several recent results starting from hardware concerns, continuing with the operating system, and ending in the applications, are integrated: the self-stabilizing microprocessor, with the self-stabilizing operating system, the self-stabilization preserving compiler, and the self-stabilizing autonomic recoverer for applications

Multivalued consensus functions defined from a vector of inputs over the set V of possible input values (and possibly from the previous input and output values) to a single output are investigated. The consensus functions are designed to tolerate t faulty inputs. Two classes of multivalued consensus functions are defined, the exact value and the range value, which require the output to be one of the nonfaulty inputs or in the range of the nonfaulty inputs, respectively. The instability of consensus functions is examined, counting the maximal number of output changes along a geodesic path of input changes, a path in which each input is changed at most once. Lower and upper bounds for the instability of multivalued consensus functions as a function of n, the number of sensors, t, and $|V|$ are presented. A new technique for obtaining such lower bounds, using edgewise simplex subdivision, is presented.

Soft errors are changes in memory value caused by external radiation or electrical noise. Decreases in computing feature sizes and power usages and shorting the microcycle period enhance the influence of soft errors. Self-stabilizing systems are designed to be started in an arbitrary, possibly a corrupted, state due to, say, soft errors, and to converge to a desired behavior. Self-stabilization is defined by the state space of the components and is essentially a well-founded, clearly defined form of the terms self-healing, automatic-recovery, automatic-repair, and autonomic-computing. To implement a self-stabilizing system, one needs to ensure that the microprocessor that executes the program is self-stabilizing. A self-stabilizing microprocessor copes with any combination of soft errors, converging to perform fetch-decode-execute in fault-free periods. Still, it is important that the microprocessor will avoid convergence periods if possible by masking the effect of soft errors immediately. In this work, we present design schemes for a self-stabilizing microprocessor and a new technique for analyzing the effect of soft errors. Previous schemes for analyzing the effect of soft errors were based on simulations. In contrast, our scheme computes a lower bound on microprocessor reliability and enables the microprocessor designer to evaluate the reliability of the design and to identify reliability bottlenecks. When analyzing the resiliency of digital circuits to soft errors, we examine the logical masking, i.e., errors in internal nodes of the circuits that are masked later by the computation. We show that the problem of computing the reliability of a circuit such that logical masking is taken into account is an NP-hard problem.

We introduce a self-stabilizing group communication system for ad hoc networks. The system design is based on a mobile agent, collecting and distributing information, during a random walk. Three possible settings for modeling the location of the mobile nodes (processors) in the ad hoc network are presented: slow location change, complete random change, and neighbors with probability. The group membership algorithm is based on a mobile agent collecting and distributing information. The new techniques support group membership and multicast, and also support resource allocation.

The task of designing algorithms for constantly changing networks is difficult. We focus on mobile ad-hoc networks, where mobile processors attempt to coordinate despite minimal infrastructure support. We develop new techniques to cope with this dynamic, heterogeneous, and chaotic environment. We mask the unpredictable behavior of mobile networks by defining and emulating a virtual infrastructure, consisting of timing-aware and location-aware machines at fixed locations, that mobile nodes can interact with. The static virtual infrastructure allows appplication developers to use simpler algorithms — including many previously developed for fixed networks. Virtual Stationary Automata programming layer. Our programming abstraction consists of a static infrastructure of fixed, timed virtual machines with an explicit notion of real time, called Virtual Stationary Automata (VSAs), distributed at known locations over the plane, and emulated by the real mobile nodes in the system. Each VSA represents a predetermined geographic area and has broadcast capabilities similar to those of the mobile nodes, allowing nearby VSAs and mobile nodes to communicate with one another. This programming layer provides mobile nodes with a virtual infrastructure with which to coordinate their actions. Many practical algorithms depend significantly on timing, and it is reasonable to assume that many mobile nodes have access to reasonably synchronized clocks. In the VSA programming layer, the virtual automata also have access to virtual clocks, guaranteed to not drift too far from real time. Our virtual infrastructure differs in key ways from others that have previously been proposed for mobile ad-hoc networks. The GeoQuorums algorithm [2] was the first to use virtual nodes; the virtual nodes in that work are atomic objects at fixed geographical locations. More general virtual mobile automata were suggested in [1]; our automata are more powerful than those in [1] in that ours include timing capabilities, which are important for many applications. Also, our automata are stationary, and are arranged in a connected pattern that is similar to a traditional wired ne-

Computerized management of critical systems makes the issues of correctness and faultless flow of long-lived and continuously-running programs extremely important e.g., [6, 7]. Complex systems cannot be fully verified because their verification may require an unreasonable amount of time and space. The software industry tests software products extensively in order to eliminate bugs as much as possible. Normally, software is tested by executing a set of large, but length-bounded and non-exhaustive scenarios starting from a predefined initial state while each scenario is defined by a set of input/output sequences. Undesired and unplanned behavior (bug) may occur due to scenarios that were not tested prior to the software release. Software malfunctions may cause damage that can outweigh the software cost. Keeping all this in mind, a consumer of a critical system would like to have a warranty that such a system will operate properly.

This work presents new directions for building a self stabilizing operating system kernel. A system is self-stabilizing [3, 4] if it can be started in any possible state and it converges to a desired behavior. A state of a system is an assignment of arbitrary values to the systems variables. The usefulness of such a system in critical and remote systems cannot be over estimated. Entire years of work maybe lost when the operating system of an expensive complicated device e.g., a spaceship, may reach an arbitrary state due to say, soft errors (e.g., [8]), and be lost forever. Last results of this research can be found in [5] and [6].

This paper presents a new abstraction for virtual infrastructure in mobile ad hoc networks. An AutonomousVirtual Mobile Node (AVMN) is a robust and reliable entity that is designed to cope with theinherent difficulties caused by processors arriving, leaving, and moving according to their own agendas,as well as with failures and energy limitations. There are many types of applications that may make useof the AVMN infrastructure: tracking, supporting mobile users, or searching for energy sources.The AVMN extends the focal point abstraction in [9] and the virtual mobile node abstraction in [10].The new abstraction is that of a virtual general-purpose computing entity, an automaton that can makeautonomous on-line decisions concerning its own movement. We describe a self-stabilizing implementationof this new abstraction that is resilient to the chaotic behavior of the physical processors and providesautomatic recovery from any corrupted state of the system.

An erasure correcting scheme is rateless if it is designed to tolerate any pattern of packet loss and reveal the information sent after a certain number of packets are received. On one hand, transmission schemes that use rateless erasure correcting usually do not use the feedback channel, however they may require an additional significant amount of processing in both the sender and the receiver sides. On the other hand, automatic repeated request (ARQ) protocols use the feedback channel to assist the sender and usually do not require information processing. In this work we present a combined approach where a lean feedback channel is used to assist the sender to efficiently transmit the information. Our real-time oblivious approach minimizes the processing and memory required at the receiver, and therefore may fit a variety of receiving devices. In addition, the transmission is real-time where the expected number of original packets revealed when a packet is received is approximately the same through the entire transmission process. We may use our end-to-end scheme as a base for broadcast (and multicast) schemes. An overlay tree structure is used to convey the information to a large number of receivers. Moreover, the receivers may download the information from a number of senders or even migrate from one sender to another.

Peer-to-peer systems are prone to faults, thus it is vitally important to design peer-to-peer systems to automatically regain consistency, namely to be self-stabilizing. Toward this goal, we present a deterministic structure that defines for every n the entire (IP) pointers structure among the n machines. Namely, the next hop for the insert, delete and search procedures of the peer-to-peer system. Thus, the consistency of the system is easily defined, monitored, verified and repaired. We present the HyperTree (distributed) structure which support the peer-to-peer procedures while ensuring that the out-degree and in-degree (the number of outgoing/incoming pointers) are b log/sub b/ N where N in the maximal number of machines and b is an integer parameter greater than 1. In addition the HyperTree ensures that the maximal number of hops involved in each procedure is bounded by log/sub b/ N. A self-stabilizing peer-to-peer system based on the HyperTree is presented.

No abstract available.

No abstract available.

No abstract available.

We initiate a study of bounded clock synchronization under a more severe fault model than that proposed by Lamport and Melliar-Smith [1985]. Realistic aspects of the problem of synchronizing clocks in the presence of faults are considered. One aspect is that clock synchronization is an on-going task, thus the assumption that some of the processors never fail is too optimistic. To cope with this reality, we suggest self-stabilizing protocols that stabilize in any (long enough) period in which less than a third of the processors are faulty. Another aspect is that the clock value of each processor is bounded. A single transient fault may cause the clock to reach the upper bound. Therefore, we suggest a bounded clock that wraps around when appropriate.We present two randomized self-stabilizing protocols for synchronizing bounded clocks in the presence of Byzantine processor failures. The first protocol assumes that processors have a common pulse, while the second protocol does not. A new type of distributed counter based on the Chinese remainder theorem is used as part of the first protocol.

This paper presents the first (randomized) algorithm for implementing self-stabilizing group communication services in an asynchronous system. Our algorithm converges rapidly to legal behavior and is communication adaptive, namely, the communication volume is high when the system recovers from the occurrence of faults and is low once a legal state is reached. Communication adaptability is achieved by a new technique that combines transient fault detectors.

No abstract available.

A self-stabilizing distributed file system is presented. The system constructs and maintains a spanning tree for each file volume. The spanning tree consists of the servers that have volume replicas and caches for the specific file volume. The spanning trees are constructed and maintained by self-stabilizing distributed algorithms. File system updates use the tree to implement file read and write operations.

We introduce a self-stabilizing group communication system for ad-hoc networks. The system design is based on random walks of mobile agents. Three possible settings for modeling the location of the processors in the ad-hoc network are presented; slow location change, complete random change, and neighbors with probability. The group membership algorithm is based on collecting and distributing information by a mobile agent. The new techniques support group membership and multicast, and also support resource allocation.

This paper proposes a new approach and new techniques for online monitoring of concurrent programs to ensure that some of their safety properties are not violated. The techniques modify erroneous systems which violate a certain safety property, into new systems which satisfy the safety property by adding a new layer that controls the scheduling of steps in the system. We formally characterize the relationship between the erroneous and the new system. Safety monitors for mutual-exclusion, l-exclusion, and the producer consumer tasks are presented. A proof for the mutual-exclusion task is presented to demonstrate the applicability of our approach. Our results are also of significance in the context of evolving systems, systems which are repeatedly modified due to changes in the user requirements, user specifications, or implementation. The monitoring technique proposed ensures that safety requirements are not violated in such evolving systems, in spite of frequent changes.

This paper introduces the notion stability for a long-lived consensus system. This notion reflects how sensitive to changes the decisions of the system are, from one invocation of the consensus algorithm to the next, with respect to input changes. Stable long-lived consensus systems are proposed, and tight lower bounds on the achievable stability are proved, for several different scenarios. The scenarios include systems that keep memory from one invocation of consensus to the next versus memoryless systems; systems that take their decisions based on the number of different inputs but not on the source identities of those inputs versus non-symmetric systems. These results intend to study essential aspects of stability, and hence are independent of specific models of distributed computing. Applications to particular asynchronous and synchronous system are described.

We examine the problem of efficient anonymous multicast and reception in general communication networks. We present algorithms that achieve anonymous communication, are protected against traffic analysis, and require O (1) amortized communication complexity on each link and low computational comlexity. The algorithms support sender anonymity, receiver(s) anonymity, or sender-receiver anonymity.

This paper explores efficient discrete coding techniques that are motivated by the time/energy tradeoff in message transmission between mobile hosts and mobile support stations. Three algorithms are suggested two of which use guessing games in which the mobile support station guesses the message to be transmitted by the mobile host and receives approving signal for successful guess from the mobile host. The first algorithm is designed to achieve the smallest expected amount of energy while obeying a time bound for message transmissions. The second algorithm achieves the shortest expected transmission time while obeying a bound on the energy. This algorithm uses dynamic programming to construct an optimal tree for the guessing game. The third algorithm uses a different approach, approach that is based on the Lempel-Ziv (1978) compression algorithm. The time energy tradeoff is controlled by the choice of the length of the codes used to encode strings in the dictionary. The theoretical results obtained are not tied to mobile computing and are of independent interest.

Scheduling ATM cells schemes for an (optical) ATM switch can dramatically influence the performance of the ATM communication network. We present an efficient scheduling that is based on perfect bipartite matching. The algorithm ensures fairness, providing a guaranteed latency bound for each arriving cell.

No abstract available.

Protocols that provide reliable communication on top of a network that can lose packets rely on periodically retransmitting packets. The choice of retransmission timeout critically affects system performance. This paper presents a first step toward a theoretical study of the choice of retransmission timeout, based on competitive analysis. In general, competitive analysis compares the performance of an on-line algorithm to the performance of an optimal off-line algorithm, which has access to more information. In this context, the job of an algorithm is to choose the retransmission timeout interval; an off-line algorithm knows the exact message delays, whereas an on-line algorithm knows only upper and lower bounds on the delays. The performance measure of interest is the expected value of a linear combination of the number of packets used and the amount of time elapsed. An on-line algorithm for choosing the retransmission timeout is presented that is optimal with respect to the difference between its performance and that of an optimal off-line algorithm. The algorithm is also analyzed with respect to the ratio of its performance and that of an optimal off-line algorithm. © 1999 John Wiley & Sons, Inc. Networks 34: 73–80, 1999

This paper presents the first dynamic routing scheme for high-speed networks. The scheme is based on a hierarchical bubbles partition of the underlying communication graph. Dynamic routing schemes are ranked by their adaptability, i.e., the maximum number of sites to be updated upon a topology change. An advantage of our scheme is that it implies a small number of updates upon a topology change. In particular, for the case of a bounded degree network it is proved that our scheme is optimal in its adaptability by presenting a matching tight lower bound. Our bubble routing scheme is a combination of a distributed routing database, a routing strategy, and a routing database update. It is shown how to perform the routing database update on a dynamic network in a distributed manner.

Motivated by the special characteristics of multimedia tasks, we consider non-preemptive scheduling of tasks where there exists no (or very limited) information concerning the tasks before they are released. We present impossibility results and analyze algorithms for non-preemptive scheduling in single processor and multiprocessor systems. In particular, one set of our results considers the competitive ratio of the scheduling algorithm when the length of the tasks is not greater than C/sub max/ (and not smaller than C/sub min/). We show that the performance of a scheduling algorithm is improved dramatically when the release time of the tasks is O(C/sub max/) prior to their deadline; achieving a competitive ratio that is close to one.

A local stabilizer protocol that takes any on-line or of-line distributed algorithm and converts it into a synchronous self-stabilizing algorithm with local monitoring and repairing properties is presented. Whenever the self-stabilizing version enters an inconsistent state, the inconsistency is detected, in O(1) time, and the system state is repaired in a local manner. The expected computation time that is lost during the repair process is proportional to the largest diameter of a faulty region.

Self-stabilizing message-driven protocols are defined and discussed. The class weak exclusion that contains many natural tasks such as $\ell$-exclusion and token passing is defined, and it is shown that in any execution of any self-stabilizing protocol for a task in this class, the configuration size must grow at least in a logarithmic rate. This last lower bound is valid even if the system is supported by a time-out mechanism that prevents communication deadlocks. Then we present three self-stabilizing message-driven protocols for token passing. The rate of growth of configuration size for all three protocols matches the aforementioned lower bound. Our protocols are presented for two-processor systems but can be easily adapted to rings of arbitrary size. Our results have an interesting interpretation in terms of automata theory.

An end-to-end data delivery protocol for dynamic communication networks is presented. The protocol uses bounded sequence numbers and can tolerate both link failures and (intermediate) processor crashes. Previous bounded end-to-end protocols could not tolerate crashes. We present a self-stabilizing version of the algorithm that can recover from crashes of the sender and the receiver as well as of intermediate processors. Starting with the network in an arbitrary state, the self-stabilizing version guarantees proper transmission of messages following a finite convergence period.

A distributed system is self-stabilizing if it can be started in any possible global state. Once started the system regains its consistency by itself, without any kind of outside intervention. The self-stabilization property makes the system tolerant to faults in which processors exhibit a faulty behavior for a while and then recover spontaneously in an arbitrary state. When the intermediate period in between one recovery and the next faulty period is long enough, the system stabilizes. A distributed system is uniform if all processors with the same number of neighbors are identical. A distributed system is dynamic if it can tolerate addition or deletion of processors and links without reinitialization. In this work, we study uniform dynamic self-stabilizing protocols for leader election under readwrite atomicity. Our protocols use randomization to break symmetry. The leader election protocol stabilizes in O(/spl Delta/D log n) time when the number of the processors is unknown and O(/spl Delta/D), otherwise. Here /spl Delta/ denotes the maximal degree of a node, D denotes the diameter of the graph and n denotes the number of processors in the graph. We introduce self-stabilizing protocols for synchronization that are used as building blocks by the leader-election algorithm. We conclude this work by presenting a simple, uniform, self-stabilizing ranking protocol.

A self-stabilizing algorithm is silent if it converges to a glc)bal state after which the values stored in the communication registers are fixed.The silence property of self-stabilizing algorithms is a desirable property in terms of simplicity and communication overhead.In this work we show that no constant memory silent self-stabilizing algorithms exist for identification of the centers of a graph, leader election, and spanning tree construction.Lower bounds of Cl(log n) bits per communication register are obtained for each of the above tasks.The existence of a silent legitimate global state that uses less than log n bits per register is assumed.This legitimate global state is used to construct a silent global state that is illegitimate.

This paper identifies the equivalence of deadlock prevention in store-and-forward communication network and simultaneous arrival of packets to a switch of bufferless high-speed network. Scheduling of packet transmission schemes, which we call baked-potato schemes, are used to avoid simultaneous arrival of packets to a switch. We present scheduling schemes for any capacity of links and switches. The schemes are evaluated by the maximal length of time between two successive scheduling of a processor. For the case of single capacity link and switch, our scheme is proved optimal by presenting a matching lower bound. Our baked-potato scheme does not assume a prior knowledge on the source destination demands and can be used for sending control packets and broadcast. Research supported in part by NSERC (Natural Sciences and Engineering Research Council of Canada) grant. y Department of Mathematics and Computer Science, Ben-Gurion University, Beer-Sheva, 84105, Israel. Email: dolev@...

Two self-stabilizing topology maintenance protocols for high-speed networks are presented. The protocols tolerate any number and kind of initial faults. The new protocols improve on previous protocols by their stabilization time (the amount of time following the last topology change required to notify every processor of the correct topology), by their utilization of limited switch bandwidth, and by their avoiding the use of unbounded sequence numbers. The first protocol stabilizes in O(log d) time in the worst case, where d is the diameter of the network. This protocol imposes a high bandwidth requirement on individual network nodes. The second, which is implemented by two software layers, reduces the processing load on individual nodes and stabilizes within O(d) time in the worst case and O(1) time when changes are infrequent.

Protocols that provide reliable communication on top of a network that can lose packets rely on periodically retransmitting packets. The choice of retransmission timeout critically affects system performance. This paper presents a first step toward a theoretical study of the choice of retransmission timeout, based on competitive analysis. In general, competitive analysis compares the performance of an on-line algorithm to the performance of an optimal off-line algorithm, which has access to more information. In this content, the job of an algorithm is to choose the retransmission timeout interval; an off-line algorithm knows the exact message delays, while an on-line algorithm only knows upper and lower bounds on the delays. The performance measure of interest is the expected value of a linear combination of the number of packets used and the amount of time elapsed. An on-line algorithm for choosing the retransmission timeout is presented that is optimal with respect to the difference between its performance and that of an optimal off-line algorithm. The algorithm is also analyzed with respect to the ratio of its performance and that of an optimal off-line algorithm.

Two aspects of reliability of distributed protocols are a protocol's ability to recover from transient faults and a protocol's ability to function in a dynamic environment. Approaches for both of these aspects have been separately developed, but have drawbacks when applied to an environment that has both transient faults and dynamic changes. This paper introduces definitions and methods for addressing both concerns in the design of systems. A protocol is superstabilizing if it is (i) self-stabilizing, meaning that it is guaranteed to respond to an arbitrary transient fault by eventually satisfying and maintaining a legitimacy predicate, and (ii) it is guaranteed to satisfy a passage predicate at all times when the system undergoes topology changes starting from a legitimate state. The passage predicate is typically a safety property that should hold while the protocol makes progress towards re-establishing legitimacy following a topology change. Specific contributions of the paper inc...

No abstract available.

This paper presents the first dynamic routing scheme for high-speed networks.The scheme is based on a hierarchical bubbles partition of the underlying communithat copym IS by perrmsslon of the Association of Computing Machinery.o cop otherwise, or to republish, requires y r a fee ancflor speci IC permission.

We introduce a novel technique, the scheduler luck game (in short sl-game) for analyzing the performance of randomized distributed protocols. We apply it in studying uniform self-stabilizing protocols for leader election under read/write atomicity. We present two protocols for the case where each processor in the system can communicate with all other processors and analyze their performance using the sl-game technique.>

Article Wait-free clock synchronization Share on Authors: Shlomi Dolev View Profile , Jennifer L. Welch View Profile Authors Info & Claims PODC '93: Proceedings of the twelfth annual ACM symposium on Principles of distributed computingSeptember 1993 Pages 97–108https://doi.org/10.1145/164051.164066Online:01 September 1993Publication History 11citation294DownloadsMetricsTotal Citations11Total Downloads294Last 12 Months3Last 6 weeks0 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 SiteGet Access

Article Resource bounds for self stabilizing message driven protocols Share on Authors: Shlomi Dolev Dept. of Computer Science, Technion, Israel Dept. of Computer Science, Technion, IsraelView Profile , Amos Israeli Dept. of Computer Science, Technion, Israel Dept. of Computer Science, Technion, IsraelView Profile , Shlomo Moran Dept. of Computer Science, Technion, Israel Dept. of Computer Science, Technion, IsraelView Profile Authors Info & Claims PODC '91: Proceedings of the tenth annual ACM symposium on Principles of distributed computingJuly 1991 Pages 281–293https://doi.org/10.1145/112600.112624Online:01 July 1991Publication History 22citation195DownloadsMetricsTotal Citations22Total Downloads195Last 12 Months4Last 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 SiteGet Access

No abstract available.