No abstract available.

No abstract available.

No abstract available.

Parallel computing on clusters of workstations and personal computers has very high \npotential, since it leverages existing hardware and software. Parallel programming \nenvironments offer the user a convenient way to express parallel computation and communication. \nIn fact, recently, a Message Passing Interface (MPI) has been proposed as an industrial \nstandard for writing "portable" message-passing parallel programs. The communication \npart of MPI consists of the usual point-to-point communication as well as collective \ncommunication. However, existing implementations of programming environments for clusters \nare built on top of a point-to-point communication layer (send and receive) over local \narea networks (LANs) and, as a result, suffer from poor performance in the collective \ncommunication part. \nIn this paper, we present an efficient design and implementation of the collective \ncommunication part in MPI that is optimized for clusters of workstations. Our system consists \nof two main components: the MPI-CCL layer that includes the collective communication \nfunctionality of MPI and a User-level Reliable Transport Protocol (URTP) that interfaces \nwith the LAN Data-link layer and leverages the fact that the LAN is a broadcast medium. \nOur system is integrated with the operating system via an efficient kernel extension \nmechanism that we developed. The kernel extension significantly improves the performance of \nour implementation as it can handle part of the communication overhead without involving \nuser space. \nWe have implemented our system on a collection of IBM RS/6000 workstations con- \nnected via a lOMbit Ethernet LAN. Our performance measurements are taken from typical \nscientific programs that run in a parallel mode by means of the MPI. The hypothesis behind \nour design is that system's performance will be bounded by interactions between the kernel \nand user space rather than by the bandwidth delivered by the LAN Data-Link Layer. Our \nresults indicate that the performance of our MPI Broadcast (on top of Ethernet) is about \ntwice as fast as a recently published software implementation of broadcast on top of ATM.

This paper gives two simple efficient distributed algorithms: one for keeping clocks in a network synchronized and one for allowing new processors to join the network with their clocks synchronized. Assuming a fault-tolerant authentication protocol, the algorithms tolerate both link and processor failures of any type. The algorithm for maintaining synchronization works for arbitrary networks (rather than just completely connected networks) and tolerates any number of processor or communication link faults as long as the correct processors remain connected by fault-free paths. It thus represents an improvement over other clock synchronization algorithms such as those of Lamport and Melliar Smith and Welch and Lynch, although, unlike them, it does require an authentication protocol to handle Byzantine faults. Our algorithm for allowing new processors to join requires that more than half the processors be correct, a requirement that is provably necessary.

While the synchronization of time-o!-day clocks ordinarily requires information f70w in both directions between the clocks, this information need not j70w directlp via messages.However, to take advantage of indirect information fiow, we have to make a number of

The goals of the RAPID environment are: firstly to make the programming of distributed protocols simple without restricting the protocol relevant choices of the programmer; secondly to provide encapsulation and reusability that are at least as powerful as those offered by object oriented programming; and thirdly to provide for different styles of programming that make RAPID an easy transitional programming environment between older and lower level languages and C. The environment provides and is programmed in the RAPID-FL subset of the functional language FL. Although the full power of FL is available to the programmer, a very small number of concepts need to be learned to program in RAPID-FL. Moreover, restriction to RAPID-FL means that one can have the safety of a functional language combined with reasonable uses of assignment. RAPID makes storage management trivial and reduces the complexity of communication management to handling a few simple commands. We describe our experience using RAPID to perform clock synchronization experiments and to serve as scaffolding for high performance C code that implements a collective communication protocol for parallel machines.>

Article Free Access Share on Early-delivery atomic broadcast Authors: Ajei Gopal Cornell University Cornell UniversityView Profile , Ray Strong IBM ARC IBM ARCView Profile , Sam Toueg Cornell University Cornell UniversityView Profile , Flaviu Cristian IBM ARC IBM ARCView Profile Authors Info & Claims PODC '90: Proceedings of the ninth annual ACM symposium on Principles of distributed computingAugust 1990 Pages 297–309https://doi.org/10.1145/93385.93430Published:01 August 1990Publication History 16citation324DownloadsMetricsTotal Citations16Total Downloads324Last 12 Months9Last 6 weeks2 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Tighter bounds are provided on the time required to reach agreement in a distributed system as a function of the failure model. After describing the model of a distributed system that is a context for this work the authors define several failure classes. They define a partial order on classes of failures that involves whether there is a latency penalty in converting from tolerance of one failure class to another. In this setting they distinguish clock and timing failures, showing that there can be a penalty in converting from timing failure tolerance to clock failure tolerance. The authors leave open the exact expression for the optimal latency for timing failure tolerant atomic broadcast, though it is conjectured that there is some penalty in converting from omission failure tolerance to timing failure tolerance.>

Two different kinds of Byzantine Agreement for distributed systems with processor faults are defined and compared. The first is required when coordinated actions may be performed by each participant at different times. This kind is called Simultaneous Byzantine Agreement (SBA). This paper deals with the number of rounds of message exchange required to reach Byzantine Agreement of either kind (BA). If an algorithm allows its participants to reach Byzantine agreement in every execution in which at most t participants are faulty, then the algorithm is said to tolerate t faults. It is well known that any BA algorithm that tolerates t faults (with t < n - 1 where n denotes the total number of processors) must run at least t + 1 rounds in some execution. However, it might be supposed that in executions where the number f of actual faults is small compared to t , the number of rounds could be correspondingly small. A corollary of our first result states that (when t < n - 1) any algorithm for SBA must run t + 1 rounds in some execution where there are no faults. For EBA (with t < n - 1), a lower bound of min( t + 1, f + 2) rounds is proved. Finally, an algorithm for EBA is presented that achieves the lower bound, provided that t is on the order of the square root of the total number of processors.

All in-text\treferences\tunderlined\tin\tblue\tare\tlinked\tto\tpublications\ton\tResearchGate, letting you\taccess\tand\tread\tthem\timmediately.

This paper gives two simple efficient distributed algorithms: one for keeping clocks in a network synchronized and one for allowing new processors to join the network with their clocks synchronized. The algorithms tolerate both link and node failures of any type. The algorithm for maintaining synchronization will work for arbitrary networks (rather than just completely connected networks) and tolerates any number of processor or communication link faults as long as the correct processors remain connected by fault-free paths. It thus represents an improvement over other clock synchronization algorithms such as [LM1,LM2,LL1]. Our algorithm for allowing new processors to join requires that more than half the processors be correct, a requirement which is provably necessary.

It is known that clock synchronization can be achieved in the presence of faulty clocks numbering more than one-third of the total number of participating clocks provided that some authentication technique is used. Without authentication the number of faults that can be tolerated has been an open question. Here we show that if we restrict logical clocks to running within some linear function of real time, then clock synchronization is impossible, without authentication, when one-third or more of the processors are faulty. However, if there is a bound on the rate at which a processor can generate messages, then we show that clock synchronization is achievable, without authentication, as long as the faults do not disconnect the network. Finally, we provide a lower bound on the closeness to which simultaneity can be achieved in the network as a function of the transmission and processing delay properties of the network.

Consider a communication network G in which a limited number of link and/or node faults F might occur. A routing ρ for the network (a fixed path between each pair of nodes) must be chosen without any knowledge of which components might become faulty. Choosing a good routing corresponds to bounding the diameter of the surviving route graph R(G,ρ)/F, where two nonfaulty nodes are joined by an edge if there are no faults on the route between them. We prove a number of results concerning the diameter of surviving route graphs. We show that if ρ is a minimal length routing, then the diameter of R(G,ρ)/F can be on the order of the number of nodes of G, even if F consists of only a single node. However, if G is the n-dimensional cube, the diameter of R(G,ρ)/F≤3 for any minimal length routing ρ and any set of faults F with |F|

This paper describes an application of Byzantine Agreement [DoSt82a, DoSt82c, LyFF82] to distributed transaction commit. We replace the second phase of one of the commit algorithms of [MoLi83] with Byzantine Agreement, providing certain trade-offs and advantages at the time of commit and providing speed advantages at the time of recovery from failure. The present work differs from that presented in [DoSt82b] by increasing the scope (handling a general tree of processes, and multi-cluster transactions) and by providing an explicit set of recovery algorithms. We also provide a model for classifying failures that allows comparisons to be made among various proposed distributed commit algorithms. The context for our work is the Highly Available Systems project at the IBM San Jose Research Laboratory [AAFKM83].

Cons~deraUon ~s given to the optunal scheduling of an SIMD (Single Instrucuon Multiple Data) machine that ~s a set of processors synchronized at the instruction level so that only one mstrucuon may be executed at a time, but that instrucuon may be executed by all or any subset of the set of processors Each processor is assumed to be executing the same program; however, since each Is operatmg on different data, each may take a different path through that program.A scheduler decides at each point m tune wluch instruction to execute next without knowledge of the future paths through the program that each processor wall take An optunal scheduler would schedule these execuuons to minimize the total execution tune (number of instructions executed).Programs for which such an opttmal scheduler exists are characterized by graph-theoreuc properties of the corresponding flow graph: They are exactly the reducible flow graphs w~th only disJoint cycles.Scheduling methods based on pnoray ordering and node listing are compared as to worst-case behavior on programs for which no optunal scheduler exists Categories and Subject Descriptors: C.1.

Reaching agreement in a distributed system in the presence of faulty processors is a central issue for reliable computer systems. Using an authentication protocol, one can limit the undetected behavior of faulty processors to a simple failure to relay messages to all intended targets. In this paper we show that, in spite of such an ability to limit faulty behavior, and no matter what message types or protocols are allowed, reaching (Byzantine) agreement requires at least $t + 1$ phases or rounds of information exchange, where t is an upper bound on the number of faulty processors. We present algorithms for reaching agreement based on authentication that require a total number of messages sent by correctly operating processors that is polynomial in both t and the number of processors, n. The best algorithm uses only $t + 1$ phases and $O(nt)$ messages.

Two different notions of Byzantine Agreement - immediate and eventually - are defined depending on whether the agreement involves an action to be performed synchronously or not. The lower bounds for time complexity depend on what kind of agreement has to be achieved. All previous algorithms to reach Byzantine Agreement ensure immediate agreement. We present two algorithms that in many cases reach the second type of agreement faster than previously known algorithms showing that there actually is a difference between the two notions: Eventual Byzantine Agreement can be reached earlier than Immediate.

Reaching agreement in a distributed system while handling malfunctioning behavior is a central issue for reliable computer systems. All previous algorithms for reaching the agreement required an exponential number of messages to be sent, with or without authentication. We give polynomial algorithms for reaching (Byzantine) agreement, both with and without the use of authentication protocols. We also prove that no matter what kind of information is exchanged, there is no way to reach agreement with fewer than t+1 rounds of exchange, where t is the upper bound on the number of faults.

Given a vector of tasks intended to execute the same program simultaneously on a machine which can execute only one instruction at a time, but can execute that instruction for any specified subset of the vector, the object is to schedule the execution to take maximal advantage of parallelism. Such a scheduling is called a vector execution scheme. A class of “perfect” programs is characterized for which such scheduling is easy and on which many vector execution schemes are optimal. This characterization shows that scheduling difficulties arise from unrestricted use of gotos producing irreducible programs, from branches in loops, and from nested loops. Once the path through the program is known for each task, it is a finite problem to find an optimal schedule; so there is an optimal vector execution scheme, even over imperfect programs. However, there is no implementable vector execution scheme which does not make use of knowledge of the future and which is optimal with respect to length of execution sequences. Some implementable vector execution schemes based on priority ordering and node sequence approaches are studied and compared as to worst case behavior on imperfect programs.

Three famdies of strategies for orgamzmg an index of ordered keys are investigated It ~s assumed either that the index is small enough to fit m mam memory or that some superstrategy orgamzes the index into pages and that search within a page is being studied Examples of strategies within the three families are B-tree Search, Binary Search, and Square Root Search The expected access times of these and other strategies are compared, and their relative merits in different indexing situations are d,scussed and conjectured on Considering time and space costs and complexity of programming, it Is concluded that a Binary Search strategy is generally preferable

Extendible hashing is a new access technique, in which the user is guaranteed no more than two page faults to locate the data associated with a given unique identifier, or key. Unlike conventional hashing, extendible hashing has a dynamic structure that grows and shrinks gracefully as the database grows and shrinks. This approach simultaneously solves the problem of making hash tables that are extendible and of making radix search trees that are balanced. We study, by analysis and simulation, the performance of extendible hashing. The results indicate that extendible hashing provides an attractive alternative to other access methods, such as balanced trees.

This paper discusses the desirability of procedure linkage optimization and sketches a general theory of interpretive semantics which is motivated by technical problems in specifying and validating program transformations that optimize procedure linkages. One particular transformation is treated in detail.Recursive ALGOL 60 procedures sometimes pass parameters by name in such a way that the general thunk mechanism is unnecessary and inefficient. We present an optimization which detects this kind of call-by-name and implements it thunklessly. We prove that the transformation preserves semantics and we discuss the effect on running time and memory management.

In this paper we give new characterizations for the flowchartability of recursive functionals. The general question of flowchartability is recursively undecidable. We present here an effective map from recursions to representatives for which the question is decidable. The decision provides a good approximation to a characterization for general flowchartability in the following senses: (1) if a representative is flowchartable then the recursions it represents are, and (2) there is a straightforward method of flowcharting, depending only on recursion structure, such that a recursion is flowchartable by this method if and only if its representative is flowchartable. The main results of the paper are (1) that such a representative is flowchartable if, and only if, it is simple or linear, and (2) that, when the context is restricted so that only invertible operations are considered, such a representative is flowchartable if, and only if, it is nested. The terms “simple” and “linear” have been defined in previous papers in the area, although they are extended slightly in this one. The term nested is introduced here. Simple, linear, and nested recursions are very easy to identify by inspection.

Abstract The Uniformly Reflexive Structure was introduced by E. G. Wagner who showed that the theory of such structures generalized much of recursive function theory. In this paper Uniformly Reflexive Structures are constructed as factor algebras of free nonassociative algebras. Wagner's question about the existence of a model with no computable splinter (“successor set”) is answered in the affirmative by the construction of a model whose only computable sets are the finite sets and their complements. Finally, for each countable Boolean algebra R of subsets of a countable set which contains the finite subsets, a model is constructed with R as its family of computable sets.