Embedded Systems November 2000 Vol13_12

Issue link:

Contents of this Issue


Page 133 of 189

Consider the case of two army generals of ancient times, when communication between distant sites could only be achieved by physically carrying messages between the sites. Note that the mismatch here is not the result of message ove rta king (al though this effect is compounded if , overtaking occurs), but is merely a consequence of the different locations of the distributed agents relative to each other. Distributed agreement problems The various fai lure scenarios in dis- tributed systems, and transmission delays in particular, have instigated important work on the foundations of distributed software. Much of thi s work has focussed on the central issue of distributed agreement. There are many variations of this problem, including time synchronization, consistent dis- tributed state, distributed mutual exclusion, distributed transactio n commit, distributed termination, dis- tributed election, and so on. However, all of these reduce to the common problem of reaching agreement in a distributed environment in the pres- ence of failures. We introduce this problem with the fo llowing apocryphal story. Consider th e case of two army generals of ancient times, when communication between distant sites could only be achieved by physically carrying mes- sages between the sites. The two gen- erals, Amphiloheus and Basi leus, are in a predicament whereby the enemy host lies between them. While neither ha the strength to single-handedly defeat the en emy, their combined force is sufficient. Thus, they must commence their attack at precisely the same time or they risk being defeated in turn. Their problem then is to agree on a time of attack. Unfortunately for them, a messen- ger going from one general to the other must pass through enemy lines with a high likelihood of being caught. Assume then, that Amphiloheus sends his messenger to Basileus with a proposed time of attack. To ensure that the message was received, he demands that the messenger return with a confirmation from Basileus. (While this is going on, Basileus could be in the process of sending his own messenger with his proposal-possibly diffe rent-for the time of the attack.) The p roblem is obvious: if the messe nger fa ils to get back to Amphiloheus, what conclusions can be reached? If the messenger suc- ceeded in reaching the othe r side but was intercepted on the way back, there is a possibili ty that Basileus will KADA:M For' Pa1 tmr ... for the· wireless, workspace Kada brings Java™ applications to the Palm V PalmVII and Palm llle, for powerful mobile workforce applications . . . The core of the Kada platform is the KadaVM, which offers the functionality of a Java Virtual Machine in a subcompact size. KadaVM eliminates PalmOS memory limitations by providing up to 6 MB of Java heap and stack space. " Calll-877-NOW-JAVA for evaluation software KADA is property of Emwerks, Inc. All other trademarks are property of their respective own< Kada fully supports awt, applet, io, util, net, text and sql packages including Object Streaming, Floating point, Class Reflection and Multi-threading capabilities KadaVM has a built-in adaptive just-in-tirr compiler that speeds up execution withou code bloat typically associated with JIT compilers.

Articles in this issue

Archives of this issue

view archives of EETimes - Embedded Systems November 2000 Vol13_12