On the message complexity of binary byzantine agreement under crash failures

Summary The binary Byzantine Agreement problem requiresn–1 receivers to agree on the binary value broadcast by a sender even when some of thesen processes may be faulty. We investigate the message complexity of protocols that solve this problem in the case of crash failures. In particular, we derive matching upper and lower bounds on the total, worst and average case number of meassages needed in the failure-free executions of such protocols.More specifically, we prove that any protocol that tolerates up tot faulty processes requires a total of at leastn+t–1 messages in its failure-free executions —and, therefore, at least [(n+t–1)/2] messages in the worst case and min (P ₀,P ₁)·(n+t–1) meassages in the average case, whereP _v is the probability that the value of the bit that the sender wants to broadcast isv. We also give protocols that solve the problem using only the minimum number of meassages for these three complexity measures. These protocols can be implemented by using 1-bit messages. Since a lower bound on the number of messages is also a lower bound on the number of meassage bits, this means that the above tight bounds on the number of messages are also tight bounds on the number of meassage bits. Vassos Hadzilacos received a BSE from Princeton University in 1980 and a PhD from Harvard University in 1984, both in Computer Science. In 1984 he joined the Department of Computer Science at the University of Toronto where he is currently an Associate Professor. In 1990–1991 he was visiting Associate Professor in the Department of Computer Science at Cornell University. His research interests are in the theory of distributed systems. Eugene Amdur obtained a B. Math from the University of Waterloo in 1986 and a M.Sc. from the University of Toronto in 1988. He is currently employed by the Vision and Robotics group at the University of Toronto in both technical and research capacities. His current areas of interest are vision, robotics, and networking. Samuel Weber received his B.Sc. in Mathematics and Computer Science and his M.Sc. in Computer Science from the University of Toronto. Currently, he is at Cornell University as a Ph.D. student in Computer Science with a minor in Psychology. His research interests include distributed systems, and the semantics of programming languages.     

Optimal asynchronous agreement and leader election algorithm for complete networks with Byzantine faulty links

Summary.  We consider agreement and leader election on asynchronous complete networks when the processors are reliable, but some of the channels are subject to failure. Fischer, Lynch, and Paterson have already shown that no deterministic algorithm can solve the agreement problem on asynchronous networks if any processor fails during the execution of the algorithm. Therefore, we consider only channel failures. The type of channel failure we consider in this paper is Byzantine failure, that is, channels fail by altering messages, sending false information, forging messages, losing messages at will, and so on. There are no restrictions on the behavior of a faulty channel. Therefore, a faulty channel may act as an adversary who forges messages on purpose to prevent the successful completion of the algorithm. Because we assume an asynchronous network, the channel delays are arbitrary. Thus, the faulty channels may not be detectable unless, for example, the faulty channels cause garbage to be sent. We present the first known agreement and leader election algorithm for asynchronous complete networks in which the processors are reliable but some channels may be Byzantine faulty. The algorithm can tolerate up to [n−22] faulty channels, where n is the number of processors in the network. We show that the bound on the number of faulty channels is optimal. When the processors terminate their corresponding algorithms, all the processors in the network will have the same correct vector, where the vector contains the private values of all the processors. Received: May 1994/Accepted: July 1995     

A Method for Patching Interleaving-Replay Attacks in Faulty Security Protocols

The verification of security protocols has attracted a lot of interest in the formal methods community, yielding two main verification approaches: i) state exploration, e.g. FDR [Gavin Lowe. Breaking and fixing the needham-schroeder public-key protocol using FDR. In TACAs'96: Proceedings of the Second International Workshop on Tools and Algorithms for Construction and Analysis of Systems, pages 147–166, London, UK, 1996. Springer-Verlag] and OFMC [A.D. Basin, S. Mödersheim, and L. Viganò. An on-the-fly model-checker for security protocol analysis. In D. Gollmann and E. Snekkenes, editors, ESORICS'03: 8th European Symposium on Research in Computer Security, number 2808 in Lecture Notes in Computer Science, pages 253–270, Gjøvik, Norway, 2003. Springer-Verlag]; and ii) theorem proving, e.g. the Isabelle inductive method [Lawrence C. Paulson. The inductive approach to verifying cryptographic protocols. Journal in Computer Security, 6(1-2):85–128, 1998] and Coral [G. Steel, A. Bundy, and M. Maidl. Attacking the asokan-ginzboorg protocol for key distribution in an ad-hoc bluetooth network using coral. In H. König, M. Heiner, and A. Wolisz, editors, IFIP TC6 /WG 6.1: Proceedings of 23rd IFIP International Conference on Formal Techniques for Networked and Distributed Systems, volume 2767, pages 1–10, Berlin, Germany, 2003. FORTE 2003 (work in progress papers)]. Complementing formal methods, Abadi and Needham's principles aim to guide the design of security protocols in order to make them simple and, hopefully, correct [M. Abadi and R. Needham. Prudent engineering practice for cryptographic protocols. IEEE Transactions on Software Engineering, 22(1):6–15, 1996]. We are interested in a problem related to verification but far less explored: the correction of faulty security protocols. Experience has shown that the analysis of counterexamples or failed proof attempts often holds the key to the completion of proofs and for the correction of a faulty model. In this paper, we introduce a method for patching faulty security protocols that are susceptible to an interleaving-replay attack. Our method makes use of Abadi and Needham's principles for the prudent engineering practice for cryptographic protocols in order to guide the location of the fault in a protocol as well as the proposition of candidate patches. We have run a test on our method with encouraging results. The test set includes 21 faulty security protocols borrowed from the Clark-Jacob library [J. Clark and J. Jacob. A survey of authentication protocol literature: Version 1.0. Technical report, Department of Computer Science, University of York, November 1997. A complete specification of the Clark-Jacob library in CAPSL is available at http://www.cs.sri.com/millen/capsl/].     

Araneola: A scalable reliable multicast system for dynamic environments

This paper presents Araneola (Araneola means “little spider” in Latin.), a scalable reliable application-level multicast system for highly dynamic wide-area environments. Araneola supports multi-point to multi-point reliable communication in a fully distributed manner, while incurring constant load (in terms of message and space complexity) on each node. For a tunable parameter k≥3, Araneola constructs and dynamically maintains a basic overlay structure in which each node’s degree is either k or k+1, and roughly 90% of the nodes have degree k. Empirical evaluation shows that Araneola’s basic overlay achieves three important mathematical properties of k-regular random graphs (i.e., random graphs in which each node has exactly k neighbors) with N nodes: (i) its diameter grows logarithmically with N; (ii) it is generally k-connected; and (iii) it remains highly connected following random removal of linear-size subsets of edges or nodes. The overlay is constructed and maintained at a low cost: each join, leave, or failure is handled locally, and entails the sending of only about 3k messages in total, independent of N. Moreover, this cost decreases as the churn rate increases.The low degree of Araneola’s basic overlay structure allows for allocating plenty of additional bandwidth for specific application needs. In this paper, we give an example for such a need — communicating with nearby nodes; we enhance the basic overlay with additional links chosen according to geographic proximity and available bandwidth. We show that this approach, i.e., a combination of random and nearby links, reduces the number of physical hops messages traverse without hurting the overlay’s robustness, as compared with completely random Araneola overlays (in which all the links are random) with the same average node degree.Given Araneola’s overlay, we sketch out several message dissemination techniques that can be implemented on top of this overlay. We present a full implementation and evaluation of a gossip-based multicast scheme, with up to 10,000 nodes. We show that compared with a (non-overlay-based) gossip-based multicast protocol, gossiping over Araneola achieves substantial improvements in load, reliability, and latency.     

Minimum Congestion Redundant Assignments to Tolerate Random Faults

Abstract. We consider the problem of computing minimum congestion, fault-tolerant, redundant assignments of messages to faulty, parallel delivery channels. In particular, we are given a set K of faulty channels, each having an integer capacity c _i and failing independently with probability f _i . We are also given a set M of messages to be delivered over K , and a fault-tolerance constraint (1-ɛ) , and we seek a redundant assignment ϕ that minimizes congestion \lilsf Cong(ϕ) , i.e. the maximum channel load, subject to the constraint that, with probability no less than (1-ɛ) , all the messages have a copy on at least one active channel. We present a polynomial-time 4-approximation algorithm for identical capacity channels and arbitrary message sizes, and a 2 \lceil\ln(|K|/\e)/\ln(1/f _max ) \rceil -approximation algorithm for related capacity channels and unit size messages. Both algorithms are based on computing a collection {K ₁ , \ldots, K _ν } of disjoint channel subsets such that, with probability no less than (1-ɛ) , at least one channel is active in each subset. The objective is to maximize the sum of the minimum subset capacities. Since the exact version of this problem is NP -complete, we provide a 2-approximation algorithm for identical capacities, and a polynomial-time (8+ \rm o (1)) -approximation algorithm for arbitrary capacities.     

Queueing analysis and optimal control of and systems

We first consider a finite-buffer single server queue where arrivals occur according to batch Markovian arrival process (BMAP). The server serves customers in batches of maximum size ‘b’ with a minimum threshold size ‘a’. The service time of each batch follows general distribution independent of each other as well as the arrival process. We obtain queue length distributions at various epochs such as, pre-arrival, arbitrary, departure, etc. Some important performance measures, like mean queue length, mean waiting time, probability of blocking, etc. have been obtained. Total expected cost function per unit time is also derived to determine the optimal value N^* of N at a minimum cost for given values of a and b. Secondly, we consider a finite-buffer single server queue where arrivals occur according to BMAP and service process in this case follows a non-renewal one, namely, Markovian service process (MSP). Server serves customers according to general bulk service rule as described above. We derive queue length distributions and important performance measures as above. Such queueing systems find applications in the performance analysis of communication, manufacturing and transportation systems.     

Optimal Adaptive Broadcasting with a Bounded Fraction of Faulty Nodes

We consider broadcasting among n processors, f of which can be faulty. A fault-free processor, called the source, holds a piece of information which has to be transmitted to all other fault-free processors. We assume that the fraction f/n of faulty processors is bounded by a constant γ<1 . Transmissions are fault free. Faults are assumed to be of the crash type: faulty processors do not send or receive messages. We use the whispering model: pairs of processors communicating in one round must form a matching. A fault-free processor sending a message to another processor becomes aware of whether this processor is faulty or fault free and can adapt future transmissions accordingly. The main result of the paper is a broadcasting algorithm working in O( log n) rounds and using O(n) messages of logarithmic size, in the worst case. This is an improvement of the result from [17] where O ((log n) ² ) rounds were used. Our method also gives the first algorithm for adaptive distributed fault diagnosis in O( log n) rounds. Received May 1997; revised May 1998.     

Non-linear protocols for optimal distributed consensus in networks of dynamic agents

We consider stationary consensus protocols for networks of dynamic agents with fixed topologies. At each time instant, each agent knows only its and its neighbors’ state, but must reach consensus on a group decision value that is function of all the agents’ initial state. We show that the agents can reach consensus if the value of such a function is time-invariant when computed over the agents’ state trajectories. We use this basic result to introduce a non-linear protocol design rule allowing consensus on a quite general set of values. Such a set includes, e.g., any generalized mean of order p of the agents’ initial states. As a second contribution we show that our protocol design is the solution of individual optimizations performed by the agents. This notion suggests a game theoretic interpretation of consensus problems as mechanism design problems. Under this perspective a supervisor entails the agents to reach a consensus by imposing individual objectives. We prove that such objectives can be chosen so that rational agents have a unique optimal protocol, and asymptotically reach consensus on a desired group decision value. We use a Lyapunov approach to prove that the asymptotical consensus can be reached when the communication links between nearby agents define a time-invariant undirected network. Finally we perform a simulation study concerning the vertical alignment maneuver of a team of unmanned air vehicles.     

On the Correctness of Goscinski′s Algorithm

In this paper, the correctness of the mutual exclusion algorithm proposed by Goscinski (J. Parallel Distribut. Comput.9(7), 77-82 (1990)), hereafter , is discussed and its features are compared with other token-based algorithms already published. In particular, we show that works correctly only using a communication system that guarantees a total ordering of messages, otherwise it is incorrect. We further give a modified version of , hereafter , and show that is actually a simple modification of the Suzuki-Kasami algorithm (ACM Trans. Comput. Systems3(5), 344-349 (1985)).     

Experimental analysis of self-organizing team’s behaviors

This paper is focused on the study of self-organizing team’s behaviors which are dependent on the interaction rules and the decision factors of team members. The self-organizing team’s behavior means that team members work unconditionally with one of the three work attitudes (diligence, average, and shirking). A small-world network is suggested as the basic relationships of team members. Different from the traditional models, Reciprocators encourage their friends if they work diligently and punish them if they shirk work. It is supposed that team member’s decision of choosing work attitude depends on four decision factors, humanity, herd instinct, rationality, and follower tendency. Firstly, all of the four decision factors’ weights are supposed as 0.25. Multiple experiments were conducted to analyze the behavior of a team by a multi-agent experiment system. It is found that, in order to increase the fraction of diligent team members, different strategies should be used under different Reciprocators’ fractions. Increasing Reciprocators’ fraction is beneficial to the increase of diligent members; however, the increase rate will slow down after an inflexion (here it means the inflexion of Reciprocators’ fraction). After the previous experiments study, extended experiments were developed to work on the influence of the four factors’ different weights. A self-adaptive algorithm is suggested to achieve the four decision factors’ weights. The results of self-adaptive algorithm have different influences on the team’s behaviors under different fractions of Reciprocators. Finally, influences of members’ different relationships are studied by other experiments. It is also proved that the fraction of diligent members is not dependent on the structure of team members’ relationships. The results demonstrate that the self-organizing team’s behavior can be significantly influenced by its scenario while managing a self-organizing team.     

Subcube Fault-Tolerance in Hypercubes

We consider the problem of determining the minimum number of faulty processors, K(n, m), and of faulty links, λ(n, m), in an n-dimensional hypercube computer so that every m-dimensional subcube is faulty. Best known lower bounds for K(n, m) and λ(n, m) are proved, several new recursive inequalities and new upper bounds are established, their asymptotic behavior for fixed m and for fixed n − m is analyzed, and their exact values are determined for small n and m. Most of the methods employed show how to construct sets of faults attaining the bounds. An extensive survey of related work is also included, showing connections to resource allocation, k-independent sets, and exhaustive testing.     

Probabilistic and nondeterministic aspects of anonymity

The concept of anonymity comes into play in a wide range of situations, varying from voting and anonymous donations to postings on bulletin boards and sending emails. The protocols for ensuring anonymity often use random mechanisms which can be described probabilistically, while the agents’ behavior may be totally unpredictable, irregular, and hence expressible only nondeterministically. Formal definitions of the concept of anonymity have been investigated in the past either in a totally nondeterministic framework, or in a purely probabilistic one. In this paper, we investigate a notion of anonymity which combines both probability and nondeterminism, and which is suitable for describing the most general situation in which the protocol and the users can have both probabilistic and nondeterministic behavior. We also investigate the properties of the definition for the particular cases of purely nondeterministic users and purely probabilistic users. We formulate the notions of anonymity in terms of probabilistic automata, and we describe protocols and users as processes in the probabilistic π-calculus, whose semantics is again based on probabilistic automata. Throughout the paper, we illustrate our ideas by using the example of the dining cryptographers.     

Publication patterns concerning the role of teams/groups in the information systems literature from 1990 to 1999

By reviewing 28 reputable journals that serve as outlets for information systems and operations management/research, 220 articles relating to information systems and teams/groups were identified over a 10-year period from 1990 through 1999. These articles were classified into 22 topic areas and subsequently cross-tabulated.The data indicate that the number of articles published in this area peaked in the mid 1990s, and that Communications of the ACM, Decision Support Systems, Information & Management, and Journal of Management Information Systems were the primary outlets. Key topic areas intersecting with teams/groups include: decision making, decision support systems, human factors, intra-organization systems, project management, telecommunications, and software. Also, connections between organizational behavior/social psychology and the current teams/groups research in information systems were discovered.     

Simple Algorithms for Multimessage Multicasting with Forwarding

We consider multimessage multicasting over the n processor complete (or fully connected) static network when the forwarding of messages is allowed. We present an efficient algorithm that constructs for every degree d problem instance a communication schedule with total communication time at most 2d , where d is the maximum number of messages that each processor may send (or receive). Our algorithm consists of two phases. In the first phase a set of communications are scheduled to be carried out in d time periods in such a way that the resulting problem is a multimessage unicasting problem of degree d . In the second phase we generate a communication schedule for this problem by reducing it to the Makespan Openshop Preemptive Scheduling problem which can be solved in polynomial time. The final schedule is the concatenation of the communication schedules for each of these two phases. For 2 ≤ l ≤ d , we present an algorithm to generate a communication schedule with total communication time at most \lfloor ( 2 - 1/l ) d \rfloor +1 , for problem instances where each processor needs to send messages to at most ld destinations. We also discuss multimessage multicasting for dynamic networks. Received September 22, 1997; revised August 29, 1998.     

Spatial strategies in a generalized spatial prisoner’s dilemma

Many strategies, such as tit-for-tat, have been proposed in the iterated prisoner’s dilemma (IPD) in which the prisoner’s dilemma (PD) is carried out repeatedly with two players. A spatial version of the iterated prisoner’s dilemma (SPD) has been studied, where a player at each site plays the IPD game with all the players in the neighborhood. However, the strategies studied in the SPD consider the past actions of a single opponent only. We studied spatial strategies that depend on the configuration of actions taken by all neighbors (as opposed to conventional temporal strategies). Since generosity can be considered as a spatial strategy, we first investigate the generosity required when an action error is involved. We also propose several spatial strategies that outperform many others.This work was presented, in part, at the 9th International Symposium on Artificial Life and Robotics, Oita, Japan, January 28–30, 2004     

Minimum Congestion Redundant Assignments to Tolerate Random Faults

We consider the problem of computing minimum congestion, fault-tolerant, redundant assignments of messages to faulty, parallel delivery channels. In particular, we are given a set Kof faulty channels, each having an integer capacity c _i and failing independently with probability f _i . We are also given a set Mof messages to be delivered over K , and a fault-tolerance constraint (1-?) , and we seek a redundant assignment ?that minimizes congestion \lilsf Cong(?) , i.e. the maximum channel load, subject to the constraint that, with probability no less than (1-?) , all the messages have a copy on at least one active channel. We present a polynomial-time 4-approximation algorithm for identical capacity channels and arbitrary message sizes, and a 2 \lceil\ln(|K|/\e)/\ln(1/f _max ) \rceil -approximation algorithm for related capacity channels and unit size messages. Both algorithms are based on computing a collection {K ₁ , \ldots, K _ν }of disjoint channel subsets such that, with probability no less than (1-?) , at least one channel is active in each subset. The objective is to maximize the sum of the minimum subset capacities. Since the exact version of this problem is NP -complete, we provide a 2-approximation algorithm for identical capacities, and a polynomial-time (8+ \rm o (1)) -approximation algorithm for arbitrary capacities.     

Reasoning about faulty quantum programs

We show how to use a programming language for formally describing and reasoning about errors in quantum computation. The formalisation is based on the concept of performing the correct operation with probability at least p, and the erroneous one with probability at most 1 − p. We apply the concept to two examples: Bell’s inequalities and the Deutsch–Jozsa quantum algorithm. The former is a fundamental thought experiment aimed at showing that Quantum Mechanics is not “local and realist”, and it is used in quantum cryptography protocols. We study it assuming faulty measurements, and we derive hardware reliability conditions that must be satisfied in order for the experiment to support its conclusions. The latter is a quantum algorithm for efficiently solving a classification problem for Boolean functions. The algorithm solves the problem with no error, but when we introduce faulty operations it becomes a two-sided error algorithm. Reasoning is accomplished via standard programming laws and quantum laws.     

Simple and efficient oracle-based consensus protocols for asynchronous Byzantine systems

This paper is on the consensus problem in asynchronous distributed systems where (up to f) processes (among n) can exhibit a Byzantine behavior, i.e., can deviate arbitrarily from their specification. One way to solve the consensus problem in such a context consists of enriching the system with additional oracles that are powerful enough to cope with the uncertainty and unpredictability created by the combined effect of Byzantine behavior and asynchrony. This paper presents two kinds of Byzantine asynchronous consensus protocols using two types of oracles, namely, a common coin that provides processes with random values and a failure detector oracle. Both allow the processes to decide in one communication step in favorable circumstances. The first is a randomized protocol for an oblivious scheduler model that assumes n > 6f. The second one is a failure detector-based protocol that assumes n > tif. These protocols are designed to be particularly simple and efficient in terms of communication steps, the number of messages they generate in each step, and the size of messages. So, although they are not optimal in the number of Byzantine processes that can be tolerated, they are particularly efficient when we consider the number of communication steps they require to decide and the number and size of the messages they use. In that sense, they are practically appealing.     

Modeling Parallel Bandwidth: Local versus Global Restrictions

Recently there has been an increasing interest in models of parallel computation that account for the bandwidth limitations in communication networks. Some models (e.g., bsp, logp, and qsm) account for bandwidth limitations using a per-processor parameter g > 1 , such that each processor can send/receive at most h messages in g . . . h time. Other models (e.g., pram(m )) account for bandwidth limitations as an aggregate parameter m < p , such that the p processors can send at most m messages in total at each step. This paper provides the first detailed study of the algorithmic implications of modeling parallel bandwidth as a per-processor (local) limitation versus an aggregate (global) limitation. We consider a number of basic problems such as broadcasting, parity, summation, and sorting, and give several new upper and lower time bounds that demonstrate the advantage of globally limited models over locally limited models given the same aggregate bandwidth (i.e., p . . . 1/g = m ). In general, globally limited models have a possible advantage whenever there is an imbalance in the number of messages sent/received by the processors. To exploit this advantage, the processors must schedule the sending of messages so as to respect the aggregate bandwidth limit. We present a new parallel scheduling algorithm for globally limited models that enable an unknown, arbitrarily unbalanced set of messages to be sent through the limited bandwidth within a (1 + ε) factor of the optimal off-line schedule with high probability, even if the penalty for overloading the network is an exponential function of the overload. We also present a near-optimal algorithm for the case where long messages must be sent as flits in consecutive time steps, as well as for the case where new messages to be sent arrive dynamically over an infinite time line. These results consider both message passing (distributed memory) and shared memory scenarios, and improve upon the best results for the locally limited model by a factor of Θ(g) . Finally, we present results quantifying the power of concurrent reads in a globally limited bandwidth setting, including showing an Ω(p lg m/m lg p) time separation between the exclusive-read and the concurrent-read pram(m ) models, which, when m << p , greatly improves upon the separation known previously. Received June 1, 1997; revised March 10,1998.