Embedded Systems November 2000 Vol13_12

Issue link:

Contents of this Issue


Page 137 of 189

I I In the Byzantine generals problem, the objective is for all the non-faulty sites to agree on a value, even if faulty sites are sending incorrect information. tion, in the form of remote procedure call or rendezvous, has the advantage of combining synchronization with communication. Once a synchronous invocation completes, the invoking party knows positively whether the communication has succeeded and, if it has, it also knows something about the state of the invoked site. For this reason, synchronous distributed com- munication primitives are directly sup- ported in many distributed languages such as Ada [10] and occam [12]. The principle is simple. In a ren- U S Software Knows Why CAD-UL is #1. U 5 Software knows who to count on when they need a partner for x86 embedded development tools. And it looks like they're not alone. According to VDC, CAD-UL is the number one revenue generator of x86 embedded development tools dezvous, for instance, one site per- forms a remote invocation while tl1e receiver executes a "receive" opera- tion. Unless the two operations are executed simultaneously, one of th e parties will have to wait for the other (which is why it is called a "ren- dezvous"). When the rendezvous occurs, the invoking site is suspended until the invoked operation is com- pleted at the remote site and a reply is received. The receiving site simply continues its execution. Unfortunately, synchronous com- munication typically involves signifi- cant overhead (mainly because of the need to deal with failures) that reduces efficiency. Furthermore, while a synchronous communication is in progress, both participants are unre- ceptive to any other communications. In many reactive and real-time sys- tems, such prolonged periods of autism are unacceptable. In contrast, asynchronous commu- nication, or message passing, is sim- pler and more efficient, but does leave the problem of synchronization to the application. Messages are simply sent to the receiver regardless of whetl1er the receiver is ready to accept them. CAD-UL U 5 SCFTWAAE. • EMBEDDED EXCELLENC E • Real-Time Operating System • Embedded TCP/IP Protocol Suite • Embedded File System • Distributed Computing (800} 356-7097 • CIC++ x86 Compiler Systems • Symbolic Debugging Systems • IDE: CAD-UL Workbench • Code Coverage Tools (877} GO CAD-UL The Byzantine generals algorithm In the Byzantine generals problem, the obj ective is for all the no n-faul ty sites to agree on a value, even if faulty sites are sending incorrect informa- tion. Furthermore, we require th at the agreed on value must be based on the information received from all other non-faulty sites. The latter is stipulated to prevent agreement on an arbitrary value but to represent a true consensus. The problem and a solution were first described by Lamport, Shostak, and Pease. [9] We assume tl1at the fol- lowing special conditions hold: 136 NOVEMBER 2000 Embedded Systems Programming

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems November 2000 Vol13_12