Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
ABS-NET: Fully Decentralized Runtime Adaptation for Distributed Objects
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.ORCID iD: 0000-0001-5432-6442
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
Reykjavik University.
2013 (English)In: Proceedings 6th Interaction and Concurrency Experience / [ed] Marco Carbone, Ivan Lanese, Alberto Lluch Lafuente, Ana Sokolova, Open Publishing Association , 2013, 85-100 p.Conference paper, Published paper (Refereed)
Abstract [en]

We present a formalized, fully decentralized runtime semantics for a core subset of ABS, a language and framework for modelling distributed object-oriented systems. The semantics incorporates an abstract graph representation of a network infrastructure, with network endpoints represented as graph nodes, and links as arcs with buffers, corresponding to OSI layer 2 interconnects. The key problem we wish to address is how to allocate computational tasks to nodes so that certain performance objectives are met. To this end, we use the semantics as a foundation for performing network-adaptive task execution via object migration between nodes. Adaptability is analyzed in terms of three Quality of Service objectives: node load, arc load and message latency. We have implemented the key parts of our semantics in a simulator and evaluated how well objectives are achieved for some application-relevant choices of network topology, migration procedure and ABS program. The evaluation suggests that it is feasible in a decentralized setting to continually meet both the objective of a node-balanced task allocation and make headway towards minimizing communication, and thus arc load and message latency.

Place, publisher, year, edition, pages
Open Publishing Association , 2013. 85-100 p.
Series
Electronic Proceedings in Theoretical Computer Science, ISSN 2075-2180 ; 131
Keyword [en]
distributed objects, routing, object mobility, adaptability
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-152217DOI: 10.4204/EPTCS.131.8OAI: oai:DiVA.org:kth-152217DiVA: diva2:749249
Conference
The 6th Interaction and Concurrency Experience workshop, Florence, Italy, the 6th of June 2013
Funder
EU, FP7, Seventh Framework Programme, FP7-231620
Note

QC 20150205

Available from: 2014-09-23 Created: 2014-09-23 Last updated: 2015-02-05Bibliographically approved
In thesis
1. Towards Correct and Efficient Program Execution in Decentralized Networks: Programming Languages, Semantics, and Resource Management
Open this publication in new window or tab >>Towards Correct and Efficient Program Execution in Decentralized Networks: Programming Languages, Semantics, and Resource Management
2014 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

The Internet as of 2014 connects billions of devices, and is expected to connect tens of billions by 2020. To meet escalating requirements, networks must be scalable, easy to manage, and be able to efficiently execute programs and disseminate data. The prevailing use of centralized systems and control in, e.g., pools of computing resources, clouds, is problematic for scalability. A promising approach to management of large networks is decentralization, where independently acting network nodes communicate with their immediate neighbors to achieve desirable results at the global level.

The research in this thesis addresses three distinct but interrelated problems in the context of cloud computing, networks, and programs running in clouds. First, we show how implementation correctness of active objects can be achieved in decentralized networks using location independent routing. Second, we investigate the feasibility of decentralized adaptive resource allocation for active objects in such networks, with promising results. Third, we automate an initial step of a process for converting programs with thread-based concurrency using shared memory to programs with message passing concurrency, which can then run efficiently in clouds.

Specifically, starting from fragments of the distributed object modeling language ABS, we give network-oblivious descriptions of runtime behavior of programs, where the global state is a flat collection of objects and method calls. We then provide network-aware semantics, that place objects on network nodes connected point-to-point by asynchronous message passing channels. By relying on location independent routing, which maps object identifiers to next-hop neighbors at each node, inter-object messages can be delivered, regardless of object mobility among nodes. We establish that network-oblivious and network-aware behavior in static networks correspond in the sense of contextual equivalence. Using a network protocol reminiscent of a two-phase commit for controlled node shutdown, we extend the approach to dynamic networks without failures.

We investigate node-local procedures for object migration to meet requirements on balanced allocations of objects to nodes, that also attempt to minimize exchange of object-related messages between nodes. By relying on coin-flips biased on local and neighbor load to decide on migration, and heuristics to capture object communication patterns, we show that balanced allocations can be achieved that make headway towards minimizing communication and latency.

Our approach to execution of object-oriented programs in networks relies on message-passing concurrency. Mainstream programming languages generally use thread-based concurrency, which relies on control-centric primitives, such as locks, for synchronization. We present an algorithm for dynamic probabilistic inference of annotations for data-centric synchronization in threaded programs. By making collections of variables in classes accessed atomically explicit, these annotations can in turn suggest objects suitable for encapsulation as a unit of message-passing concurrency.

Abstract [sv]

2014 års Internet sammankopplar miljarder enheter, och förväntas sammankoppla tiotals miljarder år 2020. För att möta eskalerande krav måste nätverk vara skalbara, enkla att underhålla, och effektivt exekvera program och disseminera data. Den nuvarande användningen av centraliserade system och kontrollmekanismer, t ex i pooler av beräkningsresurser, moln, är problematisk för skalbarhet. Ett lovande angreppssätt för att hantera storskaliga nätverk är decentralisering, där noder som agerar oberoende av varandra genom kommunikation med sina omedelbara grannar åstadkommer gynnsamma resultat på den globala nivån.

Forskningen i den här avhandlingen addresserar tre distinkta men relaterade problem i kontexten av molnsystem, nätverk och program som körs i moln. För det första visar vi hur implementationskorrekthet för aktiva objekt kan åstadkommas i decentraliserade nätverk med hjälp av platsoberoende routning. För det andra undersöker vi genomförbarheten i decentraliserad adaptiv resursallokering för aktiva objekt i sådana nätverk, med lovande resultat. För det tredje automatiserar vi ett initialt steg i en process för att konvertera program med trådbaserad samtidighet och delat minne till program med meddelandebaserad samtidighet, som då kan köras effektivt i moln.

Mer specifikt ger vi, med utgångspunkt i fragment av modelleringsspråket ABS baserat på distribuerade objekt, nätverksomedvetna beskrivningar av körningstidsbeteende för program där det globala tillståndet är en platt samling av objekt och metodanrop. Vi ger därefter nätverksmedvetna semantiker, där objekt placeras på nätverksnoder sammankopplade från punkt till punkt av asynkrona kanaler för meddelandetransmission. Genom att vid varje nod använda platsoberoende routning, som associerar objektidentifierare med grannoder som är nästa hopp, kan meddelanden mellan objekt levereras oavsett hur objekt rör sig mellan noder. Vi etablerar att nätverksomedvetet och nätverksmedvetet beteende i statiska nätverk stämmer överens enligt kontextuell ekvivalens. Genom att använda ett nätverksprotokoll som påminner om en tvåstegsförpliktelse, utökar vi vår ansats till felfria dynamiska nätverk.

Vi undersöker nodlokala procedurer för objektmigration för att möta krav på balanserade allokeringar av objekt till noder, som också försöker minimera utbyte av objektrelaterade meddelanden mellan noder. Genom att använda oss av slantsinglingar viktade efter lokal last och grannars last för att besluta om migration, och tumregler för att fånga kommunikationsmönster mellan objekt, visar vi att balanserade allokeringar, som gör framsteg mot att minimera kommunikation och tidsfördröjning, kan uppnås.

Vår ansats för exekvering av objektorienterade program i nätverk använder meddelandebaserad samtidighet. Vanligt förekommande programspråk använder sig generellt av trådbaserad samtidighet, som kräver kontrollcentrerade mekanismer, som lås, för synkronisering. Vi presenterar en algoritm som med dynamisk probabilistisk analys härleder annoteringar för datacentrerad synkronisering för trådade program. Genom att göra samlingar av variabler i klasser som läses och skrivs atomiskt explicita, kan sådana annoteringar antyda vilka objekt som är lämpliga att kapsla in som en enhet i meddelandebaserad samtidighet.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2014. xi, 43 p.
Series
TRITA-CSC-A, ISSN 1653-5723 ; 2014:16
Keyword
distributed objects, decentralization, implementation correctness, network protocols, object mobility
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-152247 (URN)978-91-7595-283-3 (ISBN)
Public defence
2014-10-24, F3, Lindstedtsvägen 26, KTH, Stockholm, 14:00 (English)
Opponent
Supervisors
Note

QC 20140929

Available from: 2014-09-29 Created: 2014-09-24 Last updated: 2014-10-03Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Authority records BETA

Dam, Mads

Search in DiVA

By author/editor
Palmskog, KarlDam, MadsLundblad, Andreas
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 52 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf