On the scalability and mean-time to failure of k resilient protocols

Consider a distributed system with nodes. A protocol running on this system is resilient if it could tolerate up to failures and operate correctly. The reliability of such a protocol is defined as the probability that no more than nodes have failed. In the first part of the paper, we study the scalability of systems running such protocols. We show the existence of a threshold time of operation for these protocols which we call the scalable mission time (SMT). This scalable mission time is the maximum time until which an asymptotic increase in the system size leads to an asymptotic increase in the reliability of the protocol. We show that beyond this scalable mission time, an asymptotic increase in system size leads to an asymptotic decrease in reliability. We also show techniques to compute the scalable mission time. In the second part of the paper, we show that the scalable mission time for a resilient protocol can be used as a good approximation to the mean-time to failure (MTTF) of the protocol, even when the failure distributions are non-exponential and the nodes fail at different rates (a heterogeneous system). We also show that the MTTF asymptotically approaches the SMT with an increase in system size . Computation of the MTTF is quite difficult when the system is heterogeneous even if the failure distribution of the nodes is exponential. Using experimental results, we show that the SMT approximation to the MTTF gives values very close to the real MTTF. Further, we consider the maintenance interval of systems running resilient protocols and show that if the maintenance interval is larger than the scalable mission time, then there is a maximum scalability value beyond which it is undesirable to scale up the size of the system. Received: 4 October 1994 / 30 May 1996     

Localized Techniques for Broadcasting in Wireless Sensor Networks

In this paper we tackle the problem of designing simple, localized, low energy consuming, reliable protocols for one-to-all communication in large scale wireless sensor networks. Our first proposed technique, called the Irrigator protocol, relies on the idea to first build a sparse overlay network, and then flood over it. The overlay network is set up by means of a simple, distributed, localized probabilistic protocol and spans all the sensor nodes with high probability. Based on the algorithmic ideas of the Irrigator protocol we then develop a second protocol, dubbed Fireworks, with similar performance that does not require any overlay network to be set up in advance. Asymptotic analytical results are provided which assess the reliability of the Irrigator and Fireworks techniques. The theoretical analysis of the proposed protocols is complemented and validated by a (simulation based) comparative performance evaluation that assesses several advantages of our new protocols with respect to gossiping and simple flooding. Differently from previous studies, we analyze and demonstrate the performance of our protocols for two different node distributions: The typical uniform distribution and a newly defined “hill” distribution, here introduced to capture some of the important and more realistic aspects of node deployment in heterogeneous terrain. Simulation results show that the proposed schemes achieve very good trade-offs between low overhead, low energy consumption and high reliability. In particular, the Irrigator and Fireworks protocols are more reliable than gossiping, and significantly reduce the number of links along which a message is sent over both flooding and gossiping.     

State and Progress in Strand Spaces: Proving Fair Exchange

Many cryptographic protocols are intended to coordinate state changes among principals. Exchange protocols, for instance, coordinate delivery of new values to the participants, i.e. additions to the set of values they possess. An exchange protocol is fair if it ensures that delivery of new values is balanced: If one participant obtains a new possession via the protocol, then all other participants will, too. Understanding this balanced coordination of different principals in a distributed system requires relating (long-term) state to (short-term) protocol activities. Fair exchange also requires progress assumptions. In this paper we adapt the strand space framework to protocols, such as fair exchange, that coordinate state changes. We regard the state as a multiset of facts, and we allow protocol actions to cause local changes in this state via multiset rewriting. Second, progress assumptions stipulate that some channels are resilient—and guaranteed to deliver messages—and some principals will not stop at critical steps. Our proofs of correctness cleanly separate protocol properties, such as authentication and confidentiality, from properties about progress and state evolution. G. Wang’s recent fair exchange protocol illustrates the approach.     

<Emphasis Type="Italic">t</Emphasis>-Private and <Emphasis Type="Italic">t</Emphasis>-Secure Auctions

In most of the auction systems the values of bids are known to the auctioneer. This allows him to manipulate the outcome of the auction. Hence, one might be interested in hiding these values. Some cryptographically secure protocols for electronic auctions have been presented in the last decade. Our work extends these protocols in several ways. On the basis of garbled circuits, i.e., encrypted circuits, we present protocols for sealed-bid auctions that fulfill the following requirements： 1） protocols are information-theoretically t-private for honest but curious parties; 2） the number of bits that can be learned by malicious adversaries is bounded by the output length of the auction; 3） the computational requirements for participating parties are very low： only random bit choices and bitwise computation of the XOR-function are necessary. Note that one can distinguish between the protocol that generates a garbled circuit for an auction and the protocol to evaluate the auction. In this paper we address both problems. We will present a t-private protocol for the construction of a garbled circuit that reaches the lower bound of 2t ＋ 1 parties, and Finally, we address the problem of bid changes in an auction. a more randomness efficient protocol for （t ＋ 1）^2 parties     

公平理性委托计算协议

已存在的安全计算集合关系的协议大多基于公钥加密算法,因此很难再嵌入到带有属性关系的公钥加密或密文搜索中.针对该问题,本文给出了非加密方法安全计算集合包含关系和集合交集的2个协议.我们首先利用（n,n）秘密共享的思想分别将原来2个问题转化为集合相等问题.在此基础上,结合离散对数,构造了安全计算集合包含关系的协议1和集合交集的协议2.最后的分析显示：我们的方案没有使用任何公钥加密方法,在保持了较优通信复杂性的同时,便于作为一种子模块嵌入到带有集合操作关系的公钥加密体制或者密文搜索体制中,从而丰富这些方案的功能.     

A Token-Based Fault-Tolerant Distributed Mutual Exclusion Algorithm

In this paper, we propose a token-based distributed mutual exclusion algorithm that is resilient to site and communication failures. The protocol uses the notion of logical time to detect the loss of the token and to recover the state of the lost token. Unlike other approaches, this results in the integration of token recovery due to failures with the protocol itself. Thus, we eliminate the need for expensive election protocols that are generally used in token-based algorithms to regenerate lost tokens. We also introduce the notion of weakly consistent replicated queues that are used to ensure freedom from starvation.     

Message logging: pessimistic, optimistic, causal, and optimal

Message-logging protocols are an integral part of a popular technique for implementing processes that can recover from crash failures. All message-logging protocols require that, when recovery is complete, there be no orphan processes, which are surviving processes whose states are inconsistent with the recovered state of a crashed process. We give a precise specification of the consistency property “no orphan processes”. From this specification, we describe how different existing classes of message-logging protocols (namely optimistic, pessimistic, and a class that we call causal) implement this property. We then propose a set of metrics to evaluate the performance of message-logging protocols, and characterize the protocols that are optimal with respect to these metrics. Finally, starting from a protocol that relies on causal delivery order, we show how to derive optimal causal protocols that tolerate f overlapping failures and recoveries for a parameter f (1⩽f⩽n)     

A Timing Assumption and Two t-Resilient Protocols for Implementing an Eventual Leader Service in Asynchronous Shared Memory Systems

This paper considers the problem of electing an eventual leader in an asynchronous shared memory system. While this problem has received a lot of attention in message-passing systems, very few solutions have been proposed for shared memory systems. As an eventual leader cannot be elected in a pure asynchronous system prone to process crashes, the paper first proposes to enrich the asynchronous system model with an additional assumption. That assumption (denoted AWB) is particularly weak. It is made up of two complementary parts. More precisely, it requires that, after some time, (1) there is a process whose write accesses to some shared variables be timely, and (2) the timers of (t−f) other processes be asymptotically well-behaved (t denotes the maximal number of processes that may crash, and f the actual number of process crashes in a run). The asymptotically well-behaved timer notion is a new notion that generalizes and weakens the traditional notion of timers whose durations are required to monotonically increase when the values they are set to increase (a timer works incorrectly when it expires at arbitrary times, i.e., independently of the value it has been set to). The paper then focuses on the design of t-resilient AWB-based eventual leader protocols. “t-resilient” means that each protocol can cope with up to t process crashes (taking t=n−1 provides wait-free protocols, i.e., protocols that can cope with any number of process failures). Two protocols are presented. The first enjoys the following noteworthy properties: after some time only the elected leader has to write the shared memory, and all but one shared variables have a bounded domain, be the execution finite or infinite. This protocol is consequently optimal with respect to the number of processes that have to write the shared memory. The second protocol guarantees that all the shared variables have a bounded domain. This is obtained at the following additional price: t+1 processes are required to forever write the shared memory. A theorem is proved which states that this price has to be paid by any protocol that elects an eventual leader in a bounded shared memory model. This second protocol is consequently optimal with respect to the number of processes that have to write in such a constrained memory model. In a very interesting way, these protocols show an inherent tradeoff relating the number of processes that have to write the shared memory and the bounded/unbounded attribute of that memory.     

Attacking Fair-Exchange Protocols: Parallel Models vs. Trace Models

Most approaches to formal protocol verification rely on an operational model based on traces of atomic actions. Modulo CSP, CCS, state-exploration, Higher Order Logic or strand spaces frills, authentication or secrecy are analyzed by looking at the existence or the absence of traces with a suitable property.We introduced an alternative operational approach based on parallel actions and an explicit representation of time. Our approach consists in specifying protocols within a logic language ( AL _SP), and associating the existence of an attack to the protocol with the existence of a model for the specifications of both the protocol and the attack.In this paper we show that, for a large class of protocols such as authentication and key exchange protocols, modeling in AL _SP is equivalent - as far as authentication and secrecy attacks are considered - to modeling in trace based models.We then consider fair exchange protocols introduced by N. Asokan et al. showing that parallel attacks may lead the trusted third party of the protocol into an inconsistent state. We show that the trace based model does not allow for the representation of this kind of attacks, whereas our approach can represent them.     

Security of a single-state semi-quantum key distribution protocol

Semi-quantum key distribution protocols are allowed to set up a secure secret key between two users. Compared with their full quantum counterparts, one of the two users is restricted to perform some “classical” or “semi-quantum” operations, which potentially makes them easily realizable by using less quantum resource. However, the semi-quantum key distribution protocols mainly rely on a two-way quantum channel. The eavesdropper has two opportunities to intercept the quantum states transmitted in the quantum communication stage. It may allow the eavesdropper to get more information and make the security analysis more complicated. In the past ten years, many semi-quantum key distribution protocols have been proposed and proved to be robust. However, there are few works concerning their unconditional security. It is doubted that how secure the semi-quantum ones are and how much noise they can tolerate to establish a secure secret key. In this paper, we prove the unconditional security of a single-state semi-quantum key distribution protocol proposed by Zou et al. (Phys Rev A 79:052312, 2009). We present a complete proof from information theory aspect by deriving a lower bound of the protocol’s key rate in the asymptotic scenario. Using this bound, we figure out an error threshold value such that for all error rates that are less than this threshold value, the secure secret key can be established between the legitimate users definitely. Otherwise, the users should abort the protocol. We make an illustration of the protocol under the circumstance that the reverse quantum channel is a depolarizing one with parameter q. Additionally, we compare the error threshold value with some full quantum protocols and several existing semi-quantum ones whose unconditional security proofs have been provided recently.     

Private and oblivious set and multiset operations

Privacy-preserving set operations are a popular research topic. Despite a large body of literature, the great majority of the available solutions are two-party protocols and expect that each participant knows her input set in the clear. In this work, we put forward a new framework for secure multi-party set and multiset operations in which the inputs can be arbitrarily partitioned among the participants, knowledge of an input (multi)set is not required for any party, and the secure set operations can be composed and can also be securely outsourced to third-party computation providers. In this framework, we construct a comprehensive suite of secure protocols for set operations and their various extensions. Our protocols are secure in the information-theoretic sense and are designed to minimize the round complexity. We then also build support for multiset operations by providing (i) a generic conversion from a multiset to a set, which makes the protocols for set operations applicable to multisets and (ii) direct instantiations of multiset operations of improved performance. All of our protocols have communication and computation complexity of \(O(m \log m)\) and logarithmic round complexity for sets or multisets of size m, which compares favorably with prior work. Practicality of our solutions is shown through experimental results, and novel optimizations based on set compaction allow us to improve performance of our protocols in practice. Our protocols are secure in both semi-honest and malicious security models.     

A Protocol for a Private Set-Operation

A new private set-operation problem is proposed. Suppose there are n parties with each owning a secret set. Let one of them, say P, be the leader, S be P＇s secret set, and t （less than n - 1） be a threshold value. For each element w of S, if w appears more than t times in the rest parties＇ sets, then P learns which parties＇ sets include w, otherwise P cannot know whether w appears in any party＇s set. For this problem, a secure protocol is proposed in the semi-honest model based on semantically secure homomorphic encryption scheme, secure sharing scheme, and the polynomial representation of sets. The protocol only needs constant rounds of communication.     

An efficient and practical threshold gateway-oriented password-authenticated key exchange protocol in the standard model

With the assistance of an authentication server, a gateway-oriented password-authenticated key exchange (GPAKE) protocol can establish a common session key shared between a client and a gateway. Unfortunately, a GPAKE protocol becomes totally insecure if an adversary can compromise the authentication server and steal the passwords of the clients. In order to provide resilience against adversaries who can hack into the authentication server, we propose a threshold GPAKE protocol and then present its security proof in the standard model based on the hardness of the decisional Diffie-Hellman (DDH) problem. In our proposal, the password is shared among n authentication servers and is secure unless the adversary corrupts more than t+1 servers. Our protocol requires n > 3t servers to work. Compared with existing threshold PAKE protocols, our protocol maintains both stronger security and greater efficiency.     

Mining spatial colocation patterns: a different framework

Recently, there has been considerable interest in mining spatial colocation patterns from large spatial datasets. Spatial colocation patterns represent the subsets of spatial events whose instances are often located in close geographic proximity. Most studies of spatial colocation mining require the specification of two parameter constraints to find interesting colocation patterns. One is a minimum prevalent threshold of colocations, and the other is a distance threshold to define spatial neighborhood. However, it is difficult for users to decide appropriate threshold values without prior knowledge of their task-specific spatial data. In this paper, we propose a different framework for spatial colocation pattern mining. To remove the first constraint, we propose the problem of finding N-most prevalent colocated event sets, where N is the desired number of colocated event sets with the highest interest measure values per each pattern size. We developed two alternative algorithms for mining the N-most patterns. They reduce candidate events effectively and use a filter-and-refine strategy for efficiently finding colocation instances from a spatial dataset. We prove the algorithms are correct and complete in finding the N-most prevalent colocation patterns. For the second constraint, a distance threshold for spatial neighborhood determination, we present various methods to estimate appropriate distance bounds from user input data. The result can help an user to set a distance for a conceptualization of spatial neighborhood. Our experimental results with real and synthetic datasets show that our algorithmic design is computationally effective in finding the N-most prevalent colocation patterns. The discovered patterns were different depending on the distance threshold, which shows that it is important to select appropriate neighbor distances.     

Information Extraction from Web Pages Using Presentation Regularities and Domain Knowledge

World Wide Web is transforming itself into the largest information resource making the process of information extraction (IE) from Web an important and challenging problem. In this paper, we present an automated IE system that is domain independent and that can automatically transform a given Web page into a semi-structured hierarchical document using presentation regularities. The resulting documents are weakly annotated in the sense that they might contain many incorrect annotations and missing labels. We also describe how to improve the quality of weakly annotated data by using domain knowledge in terms of a statistical domain model. We demonstrate that such system can recover from ambiguities in the presentation and boost the overall accuracy of a base information extractor by up to 20%. Our experimental evaluations with TAP data, computer science department Web sites, and RoadRunner document sets indicate that our algorithms can scale up to very large data sets.     

Tree regular model checking: A simulation-based approach

Regular model checking is the name of a family of techniques for analyzing infinite-state systems in which states are represented by words, sets of states by finite automata, and transitions by finite-state transducers. In this framework, the central problem is to compute the transitive closure of a transducer. Such a representation allows to compute the set of reachable states of the system and to detect loops between states. A main obstacle of this approach is that there exists many systems for which the reachable set of states is not regular. Recently, regular model checking has been extended to systems with tree-like architectures. In this paper, we provide a procedure, based on a new implementable acceleration technique, for computing the transitive closure of a tree transducer. The procedure consists of incrementally adding new transitions while merging states, which are related according to a pre-defined equivalence relation. The equivalence is induced by a downward and an upward simulation relation, which can be efficiently computed. Our technique can also be used to compute the set of reachable states without computing the transitive closure. We have implemented and applied our technique to various protocols.     

How to Prove Impossibility Under Global Fairness: On Space Complexity of Self-Stabilizing Leader Election on a Population Protocol Model

A population protocol is one of distributed computing models for passively-mobile systems, where a number of agents change their states by pairwise interactions between two agents. In this paper, we investigate the solvability of the self-stabilizing leader election in population protocols without any kind of oracles. We identify the necessary and sufficient conditions to solve the self-stabilizing leader election in population protocols from the aspects of local memory complexity and fairness assumptions. This paper shows that under the assumption of global fairness, no protocol using only n−1 states can solve the self-stabilizing leader election in complete interaction graphs, where n is the number of agents in the system. To prove this impossibility, we introduce a novel proof technique, called closed-set argument. In addition, we propose a self-stabilizing leader election protocol using n states that works even under the unfairness assumption. This protocol requires the exact knowledge about the number of agents in the system. We also show that such knowledge is necessary to construct any self-stabilizing leader election protocol.     

Closed schedulers: a novel technique for analyzing asynchronous protocols

Summary Analyzing distributed protocols in various models often involves a careful analysis of the set ofadmissible runs, for which the protocols should behave correctly. In particular, the admissible runs assumed by at-resilient protocol are runs which are fair for all but at mostt processors. In this paper we defineclosed sets of runs, and suggest a technique to prove impossibility results fort-resilient protocols, by restricting the corresponding sets of admissible runs to smaller sets, which are closed, as follows: For each protocolPR and for each initial configurationc, the set of admissible runs ofPR which start fromc defines a tree in a natural way: the root of the tree is the empty run, and each vertex in it denotes a finite prefix of an admissible run; a vertexu in the tree has a sonv iffv is also a prefix of an admissible run, which extendsu by one atomic step.The tree of admissible runs described above may contain infinite paths which are not admissible runs. A set of admissible runs isclosed if for every possible initial configurationc, each path in the tree of admissible runs starting fromc is also an admissible run. Closed sets of runs have the simple combinatorial structure of the set of paths of an infinite tree, which makes them easier to analyze. We introduce a unified method for constructing closed sets of admissible runs by using a model-independent construction of closedschedulers, and then mapping these schedulers to closed sets of runs. We use this construction to provide a unified proof of impossibility of consensus protocols. Ronit Lubitch received her B.Sc. degree in Mathematics and Computer Science from Tel Aviv University in 1989, and her Master degree in Computer Science from the Technion, in 1993. From 1992 she is working in Graffiti Software Industries, which expertise in the design and development of advanced photo realistic rendering, and animation software systems. Shlomo Moran received his B.Sc. and Ph.D. degrees in Mathematics from the Technion in 1975 and 1979 resp. In 1979–1981 he was at the University of Minnesota as a visiting research specialist. In 1981 he joined the Computer Science Department at the Technion, where he is now a full professor. In 1985–1986 he visited at IBM T.J. Watson Research Center. In 1992–1993 he visited at AT&T Bell Laboratories and in Centrum voor Wiskunde en Informatica, Amsterdam. His research interests include distributed computing, Combinatorics and Graph Theory, and Complexity Theory.A preliminary extended version of this paper appeared in the Proceedings of 6-th International Workshop on Distributed Algorithms, Haifa, November 1992This work was supported in part by the Technion V.P.R. fund. Part of this research was conducted while this author was visiting at AT&T Bell Labs at Murray Hill and at CWI, Amsterdam     

The perfectly synchronized round-based model of distributed computing

The perfectly synchronized round-based model provides the powerful abstraction of crash-stop failures with atomic and synchronous message delivery. This abstraction makes distributed programming very easy. We describe a technique to automatically transform protocols devised in the perfectly synchronized round-based model into protocols for the crash, send omission, general omission or Byzantine models. Our transformation is achieved using a round shifting technique with a constant time complexity overhead. The overhead depends on the target model: crashes, send omissions, general omissions or Byzantine failures. Rather surprisingly, we show that no other automatic non-uniform transformation from a weaker model, say from the traditional crash-stop model (with no atomic message delivery), onto an even stronger model than the general-omission one, say the send-omission model, can provide a better time complexity performance in a failure-free execution.