No description available.

In the past, techniques for specifying, verifying and implementing protocols have taken on a somewhat ad hoc (non -uniform) and informal nature. This lack of uniformity has resulted in an abundance of techniques and methodologies for analysing protocols, most of which are applicable to protocols having a small degree of complexity. Typically, different techniques are applied to various stages of a protocol development without an underlying formal basis for their integrated application. As a result, there may be no way to guarantee that subsequent stages of a development represent correct realisations of earlier ones. This thesis aims to address the problem of protocol development stated above by describing unified frameworks within which: 1) A formal theoretical foundation is laid for specifying, verifying and implementing protocols. 2) A knowledge based system is used for the formal development of a certain class of protocols. A number of limitations have been identified in the approach taken for developing the frameworks: a) The lack of 'compositional' expressiveness of the algebraic specification language. This makes it difficult to effectively analyse concurrently executing processes of protocols. b) The lack of support provided for addressing performance related issues. This makes it difficult to compare different protocols to assess their effect with respect to how long they take to achieve some data processing task. c) The protocol derivation algorithm can prove cumbersome in its application and may require a significant amount of domain knowledge (about types of 'primitives') in order to be machine automated. d) The knowledge based framework is currently limited to supporting the development of end-to-end protocols. This however is not a serious problem as the ideas and principles applied in developing these protocols form the basis for work in analysing other types. The above limitations form the basis for future work which will aim to address the problems stated. The thesis is in 5 main parts:- I) A description of various formalisms used in the past, to specify protocols. From this analysis, criteria are developed for assessing the relative merits of these formalisms, with a view towards choosing one such technique to be employed in specifying protocols. ii) A formal development of the protocol which includes a discussion of automatic theorem proving via a syntactic measure known as a trace. iii) A description of a notation with operational semantics developed for specifying and verifying protocols and services. In addition, a method utilising the notation is described whereby a service can be derived from a protocol. iv) A description of a framework within which a protocol may be verified in respect of the service it provides. v) A description of an interactive program (environment) allowing the formal development of a certain class of distributed protocols, such as the ECMA application layer protocol. The originality of this work lies in the: I) development of a methodology for automatically deriving and proving invariant properties of a specification. ii) development of a notation with operational semantics, capable of specifying and verifying distributed protocols and services. iii) identification of a means by which the correspondence between a specification and its implementation may be used as rewrite rules (not necessarily preserving all semantic information) in developing communication protocols. v) numerous algorithms described for addressing safety, liveness and conformity issues, as part of the interactive environment.

No description available.

This thesis concerns the optimization of the routing path in packet-switched computer-communication networks. Computer-communication networks over the past decade are outlined. A glossary of some of the terms used throughout this thesis are introduced. A brief description follows of the advantages of packet switching over the more conventional circuit-switched scheme for information transfer. The important design variables that a network planner is faced with in the design of these networks are discussed. A general design problem is stated and then decomposed into simpler subproblems one of which is the link-capacity assignment problem, which is briefly discussed. The route-assignment problem is identified as being of particular importance and is specified. A network model is introduced and relationships between performance measures, input parameters and constraints that appear in the general design problem are discussed. The routing problem is the formulated and a heuristic routing procedure is suggested as a sub-optimum solution to the problem. Basic routing methods are discussed. The principles of datagram and virtual circuit techniques are explained with reference to the routing of packets throughout the network. The directory routing technique with alternate routing is identified as being a specific requirement and the operation of this technique is explained in more detail. Two basic algorithms are introduced. The first which determines the shortest, second shortest, third shortest, etc., paths between all pairs of nodes in a network. The second which determines from all the paths in the first algorithm, the best alternative paths between all pairs of nodes in a network. A heuristic routing algorithm for establishing routing tables at each of the individual nodes in a packet switched data network is presented. Among the properties of a desirable routing algorithm is that the paths established between all node pairs are such that the average packet delay from source to destination node is minimal. The heuristic-routing algorithm proposed is to-be implemented on a newly proposed SAPONET packet-switching network, with special emphasis on the minimization of the average packet delay of the network. Results are presented and discussed for different combinations of the primary, secondary, tertiary and fourth alternative paths obtained. Finally, results are summarized and areas for further work identified.

Thesis (Ph. D.)--University of Texas at Austin, 1998. / Vita. Includes bibliographical references (leaves 237-254). Available also in a digital version from Dissertation Abstracts.

This work is motivated by several modern applications involving social networks, crowds, and markets. Our work focuses on the theme of designing effective incentive strategies for these applications. Viral marketing is receiving much attention by practicing marketers and researchers alike. While not a new idea, it has come to the forefront because of multiple effects – products have become more complex, making buyers to increasingly rely on opinions of their peers; consumers have evolved to distrust advertising; and Web2.0 has revolutionized the way people can connect, communicate and share. With power shifting to consumers, it has become important for companies to devise effective viral marketing strategies. Incentives are also a critical aspect of crowd sourcing tasks and play a crucial role in attracting, motivating and sustaining participation. The thesis addresses the following problems. (i) Optimal Control of Information Epidemics: We address two problems concerning information propagation in a population: a) how to maximize the spread of a given message in the population within the stipulated time and b) how to create a given level of buzz- measured by the fraction of the population engaged in conversation on a topic of interest- at a specified time horizon. (ii) Optimal Control Strategies for Social Influence (SI) Marketing: We investigate four SI strategies, namely, recommendation programs, referral programs, consumer reviews and campaigns on on-line forums. The campaign is assumed to be of finite duration, and the objective is to maximize profit, the (un-discounted) revenue minus the expenditure on the SI strategy under consideration, over the campaign duration. For each SI strategy, we focus on its timing, i.e., determining at what times to execute it. We address two important questions pertaining to them: a) how to execute a given SI strategy optimally? and b) having executed it so, what gains does it lead to? (iii) Optimal Mix of Incentive Strategies on Social Networks: The reach of a product in a pop- ulation can be influenced by offering (a) direct incentives to influence the buying behavior of potential buyers and (b) referral rewards to exploit the impact of social influence in inducing a purchasing decision. The company is interested in an optimal mix of these incentive programs. We report results on structure of optimal strategies for the company with significant practical implications. (iv) Truthful Tractable Mechanisms with Applications to Crowd sourcing: We focus on crowd- sourcing applications that involve specialized tasks for which the planner hardly has any idea about crowdworkers’ costs, for example, tagging geographical regions with air pollution levels or severity level of Ebola like disease. The mechanisms have to be robust to untruthful bidding from the crowdworkers. In our work, we propose tractable allocation algorithms that are monotone, leading to design of truthful mechanisms that can be successfully deployed in such applications.