Distributed computing

OPEN PROBLEMS

• Major open problem is to combine real-time algorithms with other needs, e.g., high performance network protocols and distributed database technology.
• What is the place of carrier-sense detection circuits in real–time system?
• If exponential back-off is used, then no guarantee is possible. (See text.)
• However, a tree-based conflict protocol, e.g., based on a site’s identifier, can guarantee message transmission.
• How should deadlocks be handled in a real-time transaction system?
• Aborting an arbitrary transaction is unacceptable.
• Aborting a low priority transaction may be acceptable.

Spatial Systems

• From a working paper by Gerard Lelann for the European Space Agency. “Problemes de communication et de coordination dans les systemes spatiaux”
• Issues for space: distributed computing (ground, space probe), delays, real-time control, failures including transient ones.

Need for Research

• Most real-time work ignores failures (Lelann’s own protocol for LANs is an exception)
• Most fault-tolerant work ignores real-time and assumes connected networks (but Earth-Mars takes 8.5 to 40 minutes and message drops are frequent).
• Distributed work generally ignores real-time too.

Hardware Failures

• Alpha particles can cause multiple bit flips and may vary (earth’s “suburbs” have fewer such particles than interplanetary space)
• Reed Solomon codes are used

Case Study: Mars Pathfinder

• Pathfinder lands on Mars.
• Silence.
• Ground control reboots.
• Transmits a while then silence.
• Repeat over a few days.
• Mission practically useless.

Case Study: Mars Pathfinder

• High priority task A and low priority task C share semaphore X.
• When C holds X a task B of intermediate priority enters but doesn’t need X.
• Net result B beats C and C never finishes.
• Every 125 ms a task N enters. It’s not supposed to see any other task. When it sees C, it resets the system. Await orders from earth.
• Priority inheritance would have fixed this.