Answers to the Midterm Exam

1. • a. Infrastructures (see http://www.pccip.gov/ )
                       
                                  

     Infrastructure	Down-time before consequences
     Information and Communications	seconds
     Electrical Power Systems	sec-min
     Gas and Oil Transportation and Storage	sec-hours
     Banking and Finance	sec-hours
     Transportation	sec-days
     Water Supply Systems	sec-hours
     Emergency Services	min-days
     Government Services	hours-days

   • b. will run indefinitely
   • c. Availability:
     - all are critical, depends on criteria
     - loss of life, property, monetary value, confidence, etc.
     - seconds to hours, depends on infrastructure and perspective
   • d. Integrity:
     - all are critically dependent on integrity
     - loss of life, property, monetary value, confidence, etc.
     - seconds to hours, depends on infrastructure and perspective
   • e. Confidentiality:
     - banking & finance, and government services have greatest dependence on confidentiality
     - most use confidentiality as a security mechanism
     - similar to or less than for availability and integrity
   • f. all, by examination and by question 1a.
   • g. all infrastructures dependent on other infrastructures
   • h. give some examples
   • i. all directly or indirectly or both
   • j. a’s depend on h’s, so can be same as attack on a’s

    

2. . Software Quality Attributes
   • a-c. (survivability:) availability, integrity, confidentiality
   • d. Efficiency
     - expectations and demand grows with capability
     - new solution become feasible at limits
     - computational resources still have cost
     - applications have real time constraints
     - their are inherent algorithmic limitations
     - distribution imposes additional communications cost
   • e. Resources vs. Requirements
     - they do: machines sit idle waiting on people
     - almost: are always barely affordable applications
     - cannot depend on identical growth rates
     - for any given set of resources, one can pick a too expensive algorithm
   • f. Survivability concerns:
     availability, integrity, confidentiality
     (Security: confidentiality, integrity, availability)
   • g. Survivability is the capability of a system to fulfill its mission, in a timely manner, in the presence of attacks, failures, or accidents. [EFL 97][FL99]
   • h. Benefits from Standards:
     - efficiencies of interoperability
     - efficient use of extant technology
     - reduced costs from mass production
   • i. Cost of Standards:
     - stronger ties to old technologies
     - greater cost of market entry for new technologies
     - reduced competition (among technologies)
     - reduced competition (from complex standards)
   • j. Formal Standards:
     - process longer than technology life cycle
     - anti-competitive exploitation of standards - through delay (vs. de facto standards) - through complexity (vs. consensus standards)

    

3. Matrix: 62 Squares
   • b. New problems may require new solution approaches.
     Focus on representation first.
     Simple solutions require appropriate representations.
   • c. Instruction Set Architectures.
     Often need unbiased independent assessment of costs and benefits.
     New problems may require new solutions.
     Efficiency and cost-effectiveness are exercises in technology trade-offs.
     Relative merits change continuously for rapidly changing technologies.
     Be skeptical of rules of thumb in technology trade-offs.
   • d. Object-oriented vs. Property-based.
     The best known and most widely used methods are not necessarily the most appropriate, efficient, etc.
     Just because ‘everyone’ knows it, does not make it true. Often need unbiased independent assessment.
     Focus on representation first.
   • e. Models vs. Abstractions. (see 3d)
   • f. Many software quality attributes. (see 3c)

    

4. • a. Correct results from inconsistent data?
   • b. Consistency among replicated dynamic data? The complete network state at any point in time?
     Examples: universe, airline reservations, power grid
     Issues: communications delay, no global oracle, limited visibility
   • c. Conclusions:
     - must manage (not eliminate) inconsistency
     - cannot have synchronized clocks
     - view all computations as long term transaction
     - focus on making best use of available information vs. understanding total picture
   • d. Implicit consensus of stakeholders.

    

5. Unbounded Network Costs
   n n nodes
   n <= 15 immediate neighbors
   n nodes initially unmarked and active n
   -each node active while at least one but not all of immediate neighbors marked
   - each active node marks one unmarked neighbor at each step
   - start by marking one node
   • a. at every step each active node marks at least one node so must eventually run out of nodes to mark
   • c. each node limited to at most 15 steps
   • d. there are n markings total by n nodes i.e. average node lifetime 1 interval
   • e. O( ln N)
   • b. O( 1 + ln N) = O(ln N)