Linking FUN and netWORKing:
Personal speculations on
making an impact
Fritz Henglein
DIKU, University of Copenhagen
[email protected]
10/3/2015
Links presentation, Edinburgh
1
Future IT

mobile, networked computing devices
with and without human interfaces (cell
phones, PDAs, terminals, hearing aids,
light switches; RFID chips, injection
controllers, routers, compute/storage
servers)
10/3/2015
Links presentation, Edinburgh
2
Future IT-system demands


All data accessible and updatable
anywhere (office, hallway, car), anytime
(7/24) by anybody [with credentials] on
any hardware platform (mainframe, pc,
pda, cell phone) and quickly (real-time)
High fault tolerance: Accessible even if
a portion of computers and network are
down.
10/3/2015
Links presentation, Edinburgh
3
Resultant future challenges

Key problems:



Providing reliable service using unreliable network
components
Data become ever more intelligent (e.g., original
HTML  HTML w/ JavaScript  ActiveX
controls/Java applets): Mobile data  mobile code
Demands will be service-oriented not deviceoriented (phone conversation, not a
telephone; tv transmission, not tv set; file
service, not file server) – decoupling of
message from (particular) messenger
10/3/2015
Links presentation, Edinburgh
4
A SWOT analysis of FUN


SWOT: Strengths, Weaknesses,
Opportunities, Threats
Or:




10/3/2015
What
What
What
What
are
are
are
are
we good at?
we not so good at?
the others not so good at?
the others good at?
Links presentation, Edinburgh
5
Strengths

Prediction: Figuring out what might happen,
before it happens; e.g., this is a worm, this is
virus, this is worthless.



Type systems, program analysis, proof carrying
code, model checking, theorem proving
Value-oriented programming (VOP): good for
distributed programming (caching, sharing,
replication, coalescing, asynchronous
computing, concurrency/transactions)
Developing “simple” (well-defined abstract,
general) programming models
10/3/2015
Links presentation, Edinburgh
6
Weaknesses:




Models (theory and technology) for
concurrency, distribution, persistent storage
A knack for backpedaling (figuring out how
things should have been done instead of
figuring out new applications)
Obsession with perfection (generality,
correctness)
Little concern for the masses
10/3/2015
Links presentation, Edinburgh
7
Opportunities





SQL is not (yet) entrenched in programming
languages: high impedance
Small networked devices operating as swarms/peerto-peer systems require new (small) operating
systems (opportunity for new designs)
Importance of predictability, in particular security,
combined with increased data intelligence
Truly mobility-transparent programming languages
still missing
Highly distributed reliable and predictable systems, in
particular peer-to-peer systems, are very hard to
build
10/3/2015
Links presentation, Edinburgh
8
Threats



Programming is a network sport (value of
network = O(n2) or O(n log n)): the masses
rule
Conventional wisdom and technology flow in
the other direction: Object-oriented, stateful
modeling, design and implementation
technology
Gigantic established update-oriented
infrastructure: hardware and OS designs are
stateful, create impedance for functional
programming
10/3/2015
Links presentation, Edinburgh
9
The Way Ahead




Focus on exploiting quality criteria of
application
Application centered, not language centered
approach: Let’s solve a difficult (new)
problem! (Not: Let’s build a new generalpurpose programming language)
Embrace and replace: Leveraging existing
(competing) technology whilst working on
making it obsolete; e.g., SQL, call-outs, locks,
sockets, SOAP, UDDI...)
KISS: Good and user-friendly plus
workarounds instead of perfect.
10/3/2015
Links presentation, Edinburgh
10
The Way Ahead



Find new chokepoint: middleware (mitigate
OS/hardware impedance)
Formalizing and integrating concurrency,
distribution, I/O, mobility, typing of updatability
Leapfrogging existing technologies and applications:

real-time communication:




one-to-one (telephony),
one-to-many (tv),
many-to-many (games)
archival communication (storing things):

many-to-many (library)
10/3/2015
Links presentation, Edinburgh
11
The Way Ahead

Maybe find collaborative applications of value
for academic world to reduce risk to
innovation by involving best-practice-oriented
actors







10/3/2015
technical report management;
journal management;
the universal research library;
e-learning platform;
maybe grid computing,
some area where P2P is valuable
inter-enterprise business processes, incl. digital
government.
Links presentation, Edinburgh
12
VOP: Value-oriented
programming

Programming with:



arbitrarily “large” values (immutable objects),
stored not only in RAM, but also on disk and on
the net
location-independent value references (short,
probabilistically unique identifiers of values,
wherever they are stored) – can be thought of as
light-weight proxies for actual (big) values
plus “small” stateful cells (mutable objects) and
cell references, incl.

10/3/2015
wait-free registers with consensus number infinity (e.g.,
compare-and-swap registers)
Links presentation, Edinburgh
13

Benefits/goals
Value references:




Arbitrarily large values:


efficient sharing of immutable data
location-independent
efficient message passing
programmatic support of efficient atomic update:
build new (global) state as value, then perform
update atomically by assigning value reference of
new value to register holding present state.
Small registers:


10/3/2015
guaranteeing atomic update, with no (or minimal)
locking
wait-freeness: ensure consensus and progress (no
process gets blocked forever or for too long) of
each client, even in the face of partial failures
14
elsewhere Links presentation, Edinburgh
Universal references
Never loaded from disk or network!
book
book
author
Susanne Staun
disk storage
10/3/2015
title
title
Blå hav
Mit smukke lig
RAM
Links presentation, Edinburgh
15
Rationale for Plan-X




Provide programming model for viewing “the
network as a single computer”.
Provide configurable software platform
(reflective middleware) that provides services
for writing applications in this model.
Encapsulate peer-to-peer routing, caching,
replication, etc., in middleware (happens
behind the scenes)
Goal: Making development of distributed,
mobile applications (almost) as simple as
development of single-computer systems.
10/3/2015
Links presentation, Edinburgh
16
Development model
main(){
app();
blob();
}
10/3/2015
Links presentation, Edinburgh
17
Execution model
10/3/2015
main(){
app();
blob();
}
Links presentation, Edinburgh
18
XML Store



Peer-to-peer persistence manager for XML
elements with simple load/store/exec
interface
Peer-to-peer architecture
Global name server for binding and rebinding
value references to human-readable names


10/3/2015
Rebinding: bindings are updated atomically.
Presently no implementation of cells
Links presentation, Edinburgh
19
Plan-X: P2P-based middleware for
distributed, mobile computing
Routing:
p2p
communica
tion/name
service
Distributed
garbage
collection
Code as
data,
remote
execution
Data
synchro
nization
and
merging
XMLStore “decorators”: request buffering,
asynchronous access, caching, socket adapters,
replication,
XMLStore core components: disk driver, in-memory
implementation
10/3/2015
Links presentation, Edinburgh
20
Scenario 1: browser/server based
communication
display X1F11F
server
put XML doc. -> ref: X1F11F
Transfers
only those
parts that
are not
already in
10/3/2015
store
XML Value Store
Links presentation, Edinburgh
client
get X1F11F
Most of
XML doc
may
already be
stored
21
locally
Scenario 2:
Replicated backup on the net
XML Store: Files
and programs,
replicated, multiple
versions
•The clients themselves are XML Store peers!
•Each file contents only stored x (e.g. 10) times
10/3/2015
Links presentation, Edinburgh
22
Scenario 3:
Dynamic application partioning
Network
p calls f via the net
proc p(f){...
proc f(u,v){...
call f(x,y)
call f(u-1,v)
...}
10/3/2015
...}
Links presentation, Edinburgh
23
Dynamic application
partioning...
Network
p calls f locally
proc p(f){...
proc f(u,v){...
proc f(u,v){...
call f(x,y)
call f(u-1,v)
call f(u-1,v)
...}
10/3/2015
...}
...}
replicate if enough space on phone
while p is executing
Links presentation, Edinburgh
24
Dynamic application
partioning...
Network
proc p(f){...
proc f(u,v){...
proc f(u,v){...
call f(x,y)
call f(u-1,v)
call f(u-1,v)
...}
10/3/2015
...}
...}
f is deleted by phone system while p is executing;
p then calls f via the net again
Links presentation, Edinburgh
25
More info

Website: www.plan-x.org




Courses/seminars on distribution and
mobility, XML, peer-to-peer systems
Student projects: XMLStore, garbage
collection, plagiarism checking, data
synchronization, etc.
Java source for (P2P) XMLStore ready to
play with
Email: [email protected]
10/3/2015
Links presentation, Edinburgh
26
OOP – or rather:
imperative programming

Basic model of programming:

primitive in-place update operations:
obj.field := obj2ref

compound update operations: controlled
sequential execution of updates; e.g.
(for int i = 0; i < arr.size; i++)
arr[i] := newVal(i);
10/3/2015
Links presentation, Edinburgh
27
Imperative programming
theme


Goal: Global state transition from State0
to Staten; State0 is destroyed.
Implementation (ephemeral state
updates):
State0 -> ... -> Statei -> Staten of
primitive state transitions, where

10/3/2015
each primitive update destroys the
previous state
Links presentation, Edinburgh
28
Consequence 1

software component interfaces are stateoriented and stateful:




which operations are available depends on history
of operations executed in the
responses from components depend on history of
operations executed
Example: Unix file I/O
NB: Operations on such components are not
necessarily atomic (or even recoverable)
10/3/2015
Links presentation, Edinburgh
29
Copy-and-update
programming
input(f)
Note:
•data get copied
•they are not always coherent
• they get copied again
process(s)
input(f)
output(f)
process(s)
output(f)
10/3/2015
Links presentation, Edinburgh
30
Why (and when) it works
(well)





no concurrent access to file
sequential and synchronous programming
(control over sequence of state changes)
no partial failures: atomic abort due to single
point of failure (single-process execution on
single processor)
no replication of stateful data
‘random’ access to location of data (rapid
access no matter where they are stored)
10/3/2015
Links presentation, Edinburgh
31
Consequence 2


Software/hardware component APIs are copyoriented: data referenced by a pointer get
copied before being manipulated to ensure
integrity
Example: Modern operating systems are
based on separation of address spaces;
require copying of data or delegation of tasks
(ask the other process to do something for
me)
10/3/2015
Links presentation, Edinburgh
32
Properties of distributed
(mobile) systems

Partial failures




can’t even distinguish network failures
from computing node failures
Concurrency
Difficult (exact) synchronization of
processes
Widely varying access latency:

10/3/2015
rpc may block arbitrarily long time
Links presentation, Edinburgh
33
Techniques for battling these
problems



Caching, replication, memoization
(buffered) asynchronous message
passing
relaxed or indeterminate semantics


time-outs
observational differences between
processes running on same machine or on
different machines
Not good for mobile code!
10/3/2015
Links presentation, Edinburgh
34
Imperative programming: Problems

caching and replication require heavy
coherence protocols or different states are
‘observable’ by clients and users


atomic (commit of compound) update is
difficult to achieve in the presence of partial
failures;


e.g. file save under NFS (wait for 30 seconds!!)
rollback is not ‘naturally’ supported, but normally
required in situations where (atomic) updates can
fail
coalescing identical data (storing data only
once) cannot be done (easily)
10/3/2015
Links presentation, Edinburgh
35
Imperative programming:
Problems...




programming is mostly synchronous to
control degree of nondeterminism due to
concurrency
access to storage locations is not ‘random’
(no modern file system does what’s shown
before)
access to updateable objects is typically
‘location’-based; mobile objects are not
‘naturally’ supported
lots of data stored multiple times
10/3/2015
Links presentation, Edinburgh
36
...but, of course

Updateable objects are excellent for
propagating information to an arbitrary
number of clients (to any caller of the
object, needn’t even know or keep track
number or identity of callers)
10/3/2015
Links presentation, Edinburgh
37
Central problem



These ops
commute!
...not reading (loading)
...not writing (saving, allocating)
but updating (overwriting)
Breaks
commuting
Note: The more updating, the less operations commute and
the more their execution needs to be controlled (synchronized).
10/3/2015
Links presentation, Edinburgh
38
Updates vs. replication

Deadlocks with replication:
O(tps2 * ta * a5 * N3 / (4 * o2)) where
N: number of replica managers
a: average number of updates per

transaction (Gray, Helland, O’Neil,
Shasha, 200x)
GHOS focused on N3, but notice a5!
10/3/2015
Links presentation, Edinburgh
39
XML Store: Basic interface

Load value:
Value load(ValueRef vr)

Save value:
ValueRef save(Value v)


(That’s it)
Security/authentication not addressed yet:


10/3/2015
extended access control based interface
encrypted storage
Links presentation, Edinburgh
40
XML Store: General interface





Equip XML stores with the ability to receive and apply
any function to itself, including any values it stores.
Called Visitor pattern in OO design
Corresponds to unique homomorphism/type
elimination rule (”fold”) known from algebraic
datatypes/type theory (or to ”apply”)
Lets XML stores not only receive single ”commands”
for execution (like ”load”, ”save”), but whole
programs.
Allows implementation of:
 query languages
 general remote processing (processing “inside” the
XML Store, e.g. for grid computing)
10/3/2015
Links presentation, Edinburgh
41
Program code as values


Program code (software) = value: Code can
be stored in the XML store.
Remote execution then involves passing a
value reference for the code to the receiver.
If the receiver already has the corresponding
value (code) – e.g. due to caching in the XML
store, no further communication is necessary;
otherwise the value is requested (pulled in)
by the receiver.
10/3/2015
Links presentation, Edinburgh
42
Basic P2P XML Store
architecture

Base configuration: each peer is a single
component made up of:



”raw” disk manager
network proxy for group of remote XML-store
peers
group communication/routing amongst peers,
presently based on:



10/3/2015
IP-multicast (Pedersen/Tejlgaard 2002), or
Chord-routing protocol (Baumann/Fennestad/Thorn
2002)
Kademlia-routing protocol (Ambus 2003)
Links presentation, Edinburgh
43
Configurable XML Store
architecture

Goal: Client applications can construct XML
Stores by constructing them from:


primitive XML stores (disk manager, in-RAM
manager, adapters to databases, file managers
etc.), and
XML store constructors (“decorators”):





10/3/2015
caching reads and writes
asynchronous load/save
buffered load/save requests
replicating store
encryption/decryption
Links presentation, Edinburgh
44
Example: replicated XML Store,
with in-memory caching
client application
replicator
cache
10/3/2015
cache
cache
Links presentation, Edinburgh
45
Example: XML Store with caching
and asynchronous writing to disk
client application
async store
cache
10/3/2015
Links presentation, Edinburgh
46
Ephemeral in-memory XML Store
client application
async store
in-memory
store
10/3/2015
ephemeral XML store
new XMLStore;
...
release XMLStore;
Links presentation, Edinburgh
47
A simple challenge




Write a little program that implements a
dictionary, e.g. for looking up phone
numbers, and inserting and updating records.
It should work on the net (concurrent
access).
It should work for a while (also after the
machine has been taken down and
restarted).
Surprisingly more complex to program than
the routines you learned in algorithm class...
10/3/2015
Links presentation, Edinburgh
48
Summary

Value-oriented model for manipulating
semistructured data:




supports light-weight caching, replication,
asynchronous computing in the “XML middleware”
Configurable XML middleware (client can
order the properties one wants from the XML
store)
Separation of program logic (in the client
code) from generic deal
Encourages clients to write transaction safe
code programmatically
10/3/2015
Links presentation, Edinburgh
49
Descargar

Document Value Model: Value-oriented programming for …