Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Service Oriented Computing and Applications
Published in: Service Oriented Computing and Applications 3-4/2015

01-09-2015 | Special Issue Paper

Location-independent routing in process network overlays

Authors: Mads Dam, Karl Palmskog

Published in: Service Oriented Computing and Applications | Issue 3-4/2015

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In distributed computing, location transparency—the decoupling of objects from their physical location—is desirable in that it can simplify application development and enables efficient resource allocation. Many systems for location transparency are built on TCP/IP. We argue that addressing mobile objects in terms of temporary hosts may not be the best design decision. Object migration makes it necessary to use dedicated routing infrastructures, e.g., location servers, to deliver inter-object messages. This incurs high costs in terms of complexity, overhead, and latency. Here, we defer object overlay routing to a networking layer, by replacing TCP/IP with a location-independent routing scheme which directs messages to destinations determined by flat identifiers instead of IP addresses. Consequently, messages are delivered directly to objects, instead of possibly out-of-date locations. We explore the scheme using a small object-based language with asynchronous message passing, similar to Core Erlang. We provide a standard, network-oblivious operational semantics of this language, and a network-aware semantics which accounts for many aspects of distribution and routing. The main result is that program execution on top of an abstract network of processing nodes connected by asynchronous point-to-point communication channels preserves network-oblivious behavior in a sound and fully abstract way, in the sense of contextual equivalence. This is a novel and strong result for such a low-level model. Previous work has addressed distributed implementations only for fully connected TCP underlays, where contextual equivalence is typically too strong, due to the need for locking to resolve preemption arising from mobility.
previous article Pabble: parameterised Scribble
next article Partially distributed coordination with Reo and constraint automata

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Appendix
Available only for authorised users
Footnotes
1
Location has interest as a source of latency, for instance, but that is another matter.
 
Literature
1.
Abadi DJ (2009) Data management in the cloud: limitations and opportunities. IEEE Data Eng Bull 32(1):3–12
2.
Arnold K (2000) The Jini specification, 2nd edn. Addison-Wesley Longman, Boston
3.
4.
Barham P, Dragovic B, Fraser K, Hand S, Harris T, Ho A, Neugebauer R, Pratt I, Warfield A (2003) Xen and the art of virtualization. In: Proceedings of the 19th ACM symposium on operating systems principles, SOSP ’03. ACM, New York, NY, USA, pp 164–177
5.
Bettini L, Bono V, De Nicola R, Ferrari G, Gorla D, Loreti M, Moggi E, Pugliese R, Tuosto E, Venneri B (2003) The Klaim project: theory and practice. In: Priami C (ed) Global computing, programming environments, languages, security, and analysis of systems, Lecture Notes in Computer Science, vol 2874. Springer, Berlin, pp 88–150
6.
Bishop S, Fairbairn M, Norrish M, Sewell P, Smith M, Wansbrough K (2005) Rigorous specification and conformance testing techniques for network protocols, as applied to TCP, UDP, and sockets. In: Proceedings of the 2005 conference on applications, technologies, architectures, and protocols for computer communications, SIGCOMM ’05. ACM, New York, NY, USA, pp 265–276
7.
8.
Caesar M, Condie T, Kannan J, Lakshminarayanan K, Stoica I (2006) ROFL: routing on flat labels. ACM SIGCOMM Comput Commun Rev 36(4):363–374CrossRef
9.
Cardelli L, Gordon AD (1998) Mobile ambients. In: Nivat M (ed) Foundations of software science and computation structures, Lecture Notes in Computer Science, vol 1378. Springer, Berlin, pp 140–155
10.
Carlsson R (2001) An introduction to Core Erlang. In: Proceedings of the PLI’01 Erlang workshop
11.
12.
13.
Clavel M, Durán F, Eker S, Lincoln P, Martí-Oliet N, Meseguer J, Quesada JF (2002) Maude: specification and programming in rewriting logic. Theor Comput Sci 285(2):187–243CrossRefMATH
14.
Conchon S, Le Fessant F (1999) Jocaml: mobile agents for objective-caml. In: Agent systems and applications, 1999 and third international symposium on mobile agents. Proceedings. First international symposium on, pp 22–29. IEEE
15.
Dam M, Palmskog K (2013) Efficient and fully abstract routing of futures in object network overlays. In: Proceedings of the 2013 workshop on programming based on actors, agents, and decentralized control, AGERE! ’13. ACM, New York, NY, USA, pp 49–60
16.
Demmer MJ, Herlihy MP (1998) The arrow distributed directory protocol. In: Kutten S (ed) Distributed computing, Lecture Notes in Computer Science, vol 1499. Springer, Berlin, pp 119–133
17.
Douglis F, Ousterhout J (1991) Transparent process migration: design alternatives and the sprite implementation. Softw Pract Exp 21(8):757–785CrossRef
18.
Field J, Varela CA (2005) Transactors: a programming model for maintaining globally consistent distributed state in unreliable environments. In: Proceedings of the 32nd ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL ’05. ACM, New York, NY, USA, pp 195–208
19.
Fournet C, Gonthier G, Levy JJ, Maranget L, Rémy D (1996) A calculus of mobile agents. In: Montanari U, Sassone V (eds) CONCUR ’96: concurrency theory, Lecture Notes in Computer Science, vol 1119. Springer, Berlin, pp 406–421
20.
Havelka D, Schulte C, Brand P, Haridi S (2005) Thread-based mobility in Oz. In: Roy P (ed) Multiparadigm programming in Mozart/Oz, Lecture Notes in Computer Science, vol 3389. Springer, Berlin, pp 137–148
21.
Henrio L, Huet F, István Z (2013) Multi-threaded active objects. In: De Nicola R, Julien C (eds) Coordination models and languages, Lecture Notes in Computer Science, vol 7890. Springer, Berlin, pp 90–104
22.
Jacobson V, Smetters DK, Thornton JD, Plass MF, Briggs NH, Braynard RL (2009) Networking named content. In: Proceedings of the 5th international conference on emerging networking experiments and technologies, CoNEXT ’09. ACM, New York, NY, USA, pp 1–12
23.
24.
25.
Johnsen EB, Hähnle R, Schäfer J, Schlatte R, Steffen M (2012) ABS: a core language for abstract behavioral specification. In: Aichernig BK, de Boer FS, Bonsangue MM (eds) Formal methods for components and objects, Lecture Notes in Computer Science, vol 6957. Springer, Berlin, pp 142–164
26.
Johnsen EB, Owe O, Yu IC (2006) Creol: a type-safe object-oriented model for distributed concurrent systems. Theor Comput Sci 365(1–2):23–66MathSciNetCrossRefMATH
27.
Johnsen EB, Schlatte R, Tapia Tarifa SL (2012) A formal model of object mobility in resource-restricted deployment scenarios. In: Arbab F, Ölveczky PC (eds) Formal aspects of component software, Lecture Notes in Computer Science, vol 7253. Springer, Berlin, pp. 187–204
28.
Jul E, Levy H, Hutchinson N, Black A (1988) Fine-grained mobility in the Emerald system. ACM Trans Comput Syst 6(1):109–133
29.
Klein G, Elphinstone K, Heiser G, Andronick J, Cock D, Derrin P, Elkaduwe D, Engelhardt K, Kolanski R, Norrish M, Sewell T, Tuch H, Winwood S (2009) seL4: formal verification of an OS kernel. In: Proceedings of the ACM SIGOPS 22nd symposium on operating systems principles, SOSP ’09. ACM, New York, NY, USA, pp 207–220
30.
Lienhardt M, Schmitt A, Stefani JB (2007) Oz/K: a kernel language for component-based open programming. In: Proceedings of the 6th international conference on Generative programming and component engineering, GPCE ’07. ACM, New York, NY, USA, pp 43–52
31.
Marinos I, Watson RNM, Handley M (2013) Network stack specialization for performance. In: Proceedings of the twelfth ACM workshop on hot topics in networks, HotNets-XII. ACM, New York, NY, USA, pp 9:1–9:7
32.
Mechitov K, Razavi R, Agha G (2007) Architecture design principles to support adaptive service orchestration in WSN applications. ACM SIGBED Rev 4(3):37–42CrossRef
33.
Milner R, Parrow J, Walker D (1992) A calculus of mobile processes, I and II. Inf Comput 100(1):1–40, 41–77
34.
Nestmann U, Fuzzati R, Merro M (2003) Modeling consensus in a process calculus. In: Amadio R, Lugiez D (eds) CONCUR 2003—concurrency theory, Lecture Notes in Computer Science, vol 2761. Springer, Berlin, pp 399–414. doi:10.​1007/​978-3-540-45187-7_​26
35.
Palmskog K (2014) Towards correct and efficient program execution in decentralized networks: programming languages, semantics, and resource management. Ph.D. thesis, KTH Royal Institute of Technology
36.
Palmskog K, Dam M, Lundblad A, Jafari A (2013) ABS-NET: fully decentralized runtime adaptation for distributed objects. In: Carbone M, Lanese I, Lafuente AL, Sokolova A (eds) Proceedings 6th interaction and concurrency experience, Florence, Italy, 6th June 2013, electronic proceedings in theoretical computer science, vol 131. Open Publishing Association, pp 85–100
37.
Papazoglou MP, Traverso P, Dustdar S, Leymann F (2008) Service-oriented computing: a research roadmap. Int J Coop Inf Syst 17(02):223–255CrossRef
38.
Parrow J, Sjödin P (1996) Designing a multiway synchronization protocol. Comput Commun 19(14):1151–1160CrossRef
39.
Pierce BC, Turner DN (2000) Pict: A programming language based on the pi-calculus. In: Plotkin G, Stirling C, Tofte M (eds) Proof, language and interaction: essays in honour of Robin Milner. MIT Press, Cambridge, MA, USA, pp 455–494
40.
Pitts AM (2011) Howe’s method for higher-order languages. In: Sangiorgi D, Rutten JJMM (eds) Advanced topics in bisimulation and coinduction, Cambridge tracts in theoretical computer science, vol 52, Chap 5. Cambridge University Press, Cambridge, pp 197–232
41.
Sangiorgi D, Kobayashi N, Sumii E (2011) Environmental bisimulations for higher-order languages. ACM Trans Program Lang Syst 33(1):5:1–5:69
42.
Schaefer I, Hähnle R (2011) Formal methods in software product line engineering. IEEE Comput 44(2):82–85
43.
Schäfer J (2010) A programming model and language for concurrent and distributed object-oriented systems. Ph.D. thesis, University of Kaiserslautern
44.
Sewell P, Wojciechowski PT, Unyapoth A (2010) Nomadic pict: programming languages, communication infrastructure overlays, and semantics for mobile computation. ACM Trans Program Lang Syst 32(4):12:1–12:63CrossRef
45.
Singla A, Godfrey PB, Fall K, Iannaccone G, Ratnasamy S (2010) Scalable routing on flat names. In: Proceedings of the 6th international conference on emerging networking experiments and technologies, CoNEXT ’10. ACM, New York, NY, USA, pp 20:1–20:12
46.
Skeen D, Stonebraker M (1983) A formal model of crash recovery in a distributed system. IEEE Trans Softw Eng 9(3):219–228CrossRef
47.
Smolka G (1995) The definition of Kernel Oz. In: Podelski A (ed) Constraint programming: basics and trends, Lecture Notes in Computer Science, vol 910. Springer, Berlin, pp 251–292
48.
van Steen M, Hauck FJ, Ballintijn G, Tanenbaum AS (1998) Algorithmic design of the globe wide-area location service. Comput J 41(5):297–310CrossRefMATH
49.
Tanenbaum A (2002) Computer networks, 4th edn. Prentice Hall Professional Technical Reference, Upper Saddle River
50.
Wang WJ, Varela CA (2006) Distributed garbage collection for mobile actor systems: the pseudo root approach. In: Chung YC, Moreira J (eds) Advances in grid and pervasive computing, Lecture Notes in Computer Science, vol 3947. Springer, Berlin, pp 360–372
51.
Wei Y, Blake M (2010) Service-oriented computing and cloud computing: challenges and opportunities. IEEE Internet Comput 14(6):72–75CrossRef
Metadata
Title
Location-independent routing in process network overlays
Authors
Mads Dam
Karl Palmskog
Publication date
01-09-2015
Publisher
Springer London
Published in
Service Oriented Computing and Applications / Issue 3-4/2015
Print ISSN: 1863-2386
Electronic ISSN: 1863-2394
DOI
https://doi.org/10.1007/s11761-014-0173-7

Other articles of this Issue 3-4/2015

Service Oriented Computing and Applications 3-4/2015 Go to the issue

Special Issue Paper

Partially distributed coordination with Reo and constraint automata

Special Issue Paper

Self-adaptive multiparty sessions

Special Issue Paper

On the behaviour of general purpose applications on cloud storages

Guest Editorial

Preface

Special Issue Paper

A formalized framework for mobile cloud computing

Special Issue Paper

Pabble: parameterised Scribble

Premium Partner

    Image Credits