Protocol for Synchronizations between Distributed Processes Connected by a BinaryTree Connection Network

摘要

In this report the P2L3S protocol is presented that realizes point-to-pointsynchronous inter-process communication within a collection of processes, connected by a binary tree connection network. The protocol assumes a distributed address space, symmetrical unawareness of synchronization partners and employs a restricted form of broadcasting, called multicasting. In worst-cases the protocol establishes synchronizations in sublinear time with respect to the total number of processes. The protocol studied in this report is developed to serve as inter-process communication paradigm for implementations of Communicating Sequential Processes (CSP) and Calculus of Communicating Systems (CCS) alike languages in a distributed environment. The terms that are used within the context of the protocol are defined in section 2. The protocol, consisting of a tree walk, is presented in section 3. Section 4 treats some key properties concerning termination and the functionality of the protocol. The report is closed with some observations.