Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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
Towards Correct and Efficient Program Execution in Decentralized Networks: Programming Languages, Semantics, and Resource Management
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
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 [en]
distributed objects, decentralization, implementation correctness, network protocols, object mobility
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-152247ISBN: 978-91-7595-283-3 (print)OAI: oai:DiVA.org:kth-152247DiVA: diva2:749552
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
List of papers
1. Location Independent Routing in Process Network Overlays
Open this publication in new window or tab >>Location Independent Routing in Process Network Overlays
2014 (English)In: Service Oriented Computing and Applications, ISSN 1863-2386, E-ISSN 1863-2394, no Special Issue, 1-25 p.Article in journal (Other academic) Published
Abstract [en]

In distributed computing, location transparency - the decoupling of objects, tasks, and virtual machines from their physical location - is desirable in that it can simplify application development and management, and enable load balancing and efficient resource allocation. Many existing systems for location transparency are built on top of TCP/IP. We argue that addressing mobile objects in terms of the host where they temporarily reside may not be the best design decision. When objects can migrate, it becomes necessary to use a dedicated routing infrastructure to deliver inter-object messages, such as location servers or forwarding chains. This incurs high costs in terms of complexity, overhead, and latency. In this paper, we defer object overlay routing to an underlying networking layer, by assuming a location independent routing scheme in place of TCP/IP. In this scheme, messages are directed to destinations determined by flat identifiers instead of IP addresses. Consequently, messages are delivered directly to a recipient object, instead of a possibly out-of-date location. We explore the scheme in the context of a small object-based language with asynchronous message passing, in the style of core Erlang. We provide a standard, network-oblivious operational semantics of this language, and a network-aware semantics which takes many aspects of distribution and message routing into account. The main result is that execution of a program on top of an abstract network of processing nodes connected by asynchronous point-to-point communication channels preserves the 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 in terms of fully connected TCP underlays. But in this setting, contextual equivalence is typically too strong, due to the need for locking to resolve preemption arising from object mobility.

Keyword
distributed systems, network protocols, routing, object mobility, semantics of programming languages
National Category
Computer Science
Research subject
SRA - ICT
Identifiers
urn:nbn:se:kth:diva-131378 (URN)10.1007/s11761-014-0173-7 (DOI)2-s2.0-84945480958 (Scopus ID)
Funder
EU, FP7, Seventh Framework Programme, 6854
Note

QC 20150209

Available from: 2013-10-14 Created: 2013-10-14 Last updated: 2017-12-06Bibliographically approved
2. Efficient and Fully Abstract Routing of Futures in Object Network Overlays
Open this publication in new window or tab >>Efficient and Fully Abstract Routing of Futures in Object Network Overlays
(English)Manuscript (preprint) (Other academic)
Abstract [en]

In distributed object systems, it is desirable to enable migration of objects between locations, e.g., in order to support efficient resource allocation. Existing approaches build complex routing infrastructures to handle object-to-object communication, typically on top of IP, using, e.g., message forwarding chains or centralized object location servers. These solutions are costly and problematic in terms of efficiency, overhead, and correctness. We show how location independent routing can be used to implement object overlays with complex messaging behavior in a sound, fully abstract, and efficient way, on top of an abstract network of processing nodes connected point-to-point by asynchronous channels. We consider a distributed object language with futures, essentially lazy return values. Futures are challenging in this context due to the strong global consistency requirements they impose. The key conclusion is that execution in a decentralized, asynchronous network can preserve the standard, network-oblivious behavior of objects with futures, in the sense of contextual equivalence. To the best of our knowledge, this is the first such result in the literature. We also believe the proposed execution model may be of interest in its own right in the context of large-scale distributed computing.

Keyword
distributed objects, programming languages, network protocols, routing, futures, object mobility
National Category
Computer Science
Research subject
SRA - ICT
Identifiers
urn:nbn:se:kth:diva-132193 (URN)
Funder
EU, FP7, Seventh Framework Programme, 6854
Note

QS 2014

Available from: 2013-10-23 Created: 2013-10-23 Last updated: 2014-09-29Bibliographically approved
3. ABS-NET: Fully Decentralized Runtime Adaptation for Distributed Objects
Open this publication in new window or tab >>ABS-NET: Fully Decentralized Runtime Adaptation for Distributed Objects
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
Series
Electronic Proceedings in Theoretical Computer Science, ISSN 2075-2180 ; 131
Keyword
distributed objects, routing, object mobility, adaptability
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-152217 (URN)10.4204/EPTCS.131.8 (DOI)
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
4. Decentralized Adaptive Power Control for Process Networks
Open this publication in new window or tab >>Decentralized Adaptive Power Control for Process Networks
(English)Manuscript (preprint) (Other academic)
Abstract [en]

Mobility and location transparency of distributed objects enable efficient resource allocation in networks, and can be effectively realized at the language level using location independent routing. However, the benefits of mobility are restricted by the available resources, e.g., in the form of processing nodes, which may be too few or too many to suit an application. To continually meet an application developer's requirements on computational task throughput, and an infrastructure provider's requirements on energy usage, the network itself must be able to adapt. In this paper, we consider fault-free networks of nodes connected point-to-point by asynchronous message passing channels, and propose a protocol for shutdown of nodes that preserves the integrity of distributed objects. This protocol enables decentralized power control, where nodes are turned on and off in response to computational requirements. We analyze the protocol both by verifying a restricted version in the model checker Spin, and by formulating a transition system model and proving properties by induction in that model for networks of arbitrary size. We define a protocol extension that, while using only a node's neighborhood-local information, is sufficient to ensure networks remain connected after node shutdown, and outline more complex, general local criteria. Finally, we discuss heuristics for node-local decision making on initiating a shutdown process, to meet adaptability requirements.

Keyword
power control, object mobility, network protocols, adaptability
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-152240 (URN)
Note

QS 2014

Available from: 2014-09-24 Created: 2014-09-24 Last updated: 2014-09-29Bibliographically approved
5. Dynamic Probabilistic Inference of Atomic Sets
Open this publication in new window or tab >>Dynamic Probabilistic Inference of Atomic Sets
(English)Manuscript (preprint) (Other academic)
Abstract [en]

Concurrent programs often ensure the consistency of their data structures through synchronization.  Because control-centric synchronization primitives, such as locks, are disconnected from the consistency invariants of the data structures, a compiler cannot check and and enforce these invariants - making it hard to detect bugs caused by incorrect synchronization. Moreover, a consistency bug may be the result of some unlikely schedule and therefore not show up in program testing.  In contrast, data-centric synchronization adds annotations to data structures, defining sets of fields that must be accessed atomically. A compiler can check such annotations for consistency, detect deadlock, and automatically add primitives to prevent data races. However, annotating existing code is time consuming and error prone because it requires understanding the concurrency semantics implemented in the code. We propose a novel algorithm, called BAIT, for deriving such annotations automatically from observed program executions using Bayesian probabilistic inference. The algorithm produces atomic set, unit of work, and alias annotations for atomic-set based synchronization. Using our implementation of the algorithm, we have derived annotations for large code bases, for example the Java collections framework, in a matter of seconds. A comparison of the inferred annotations against manually converted programs, and two case studies on large, widely-used programs, show that our implementation derives detailed annotations of high quality.

Keyword
atomic sets, data-centric synchronization, bayesian inference
National Category
Computer Science
Research subject
Computer Science
Identifiers
urn:nbn:se:kth:diva-152241 (URN)
Note

QS 2014

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

Open Access in DiVA

doctoral-thesis-karl-palmskog.pdf(2012 kB)628 downloads
File information
File name FULLTEXT03.pdfFile size 2012 kBChecksum SHA-512
3374e96da53c92c0ca77d187edc446c19539dfbcfa7df56d4311d96ac0e13253eba90732f98706da39f72d1f234902a0f3600f50290363d227455434cbfdf7ba
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Palmskog, Karl
By organisation
Theoretical Computer Science, TCS
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 634 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 4002 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • 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