Abstract Vector clock algorithms are fundamental wait-free building blocks that enable the causal ordering of events. As wait-free algorithms, they are designed to complete their operations within a finite number of steps. Stabilizing algorithms aid the system in recovering after the occurrence of transient faults, such as soft errors and arbitrary violations of the assumptions according to which the system was designed to behave. To the best of our knowledge, this paper introduces the first stabilizing vector clock algorithm for asynchronous crash-prone message-passing systems that can achieve wait-free recovery after the occurrence of transient faults. In such settings, demonstrating finite and wait-free recovery from transient faults as well as communication and crash failures, bounding the message and storage sizes, handling the removal of stale information without blocking, and addressing concurrent counter overflow events at different network nodes pose significant challenges. We propose an algorithm that ensures safety in the absence of transient faults and offers bounded time recovery during fair executions following the last transient fault. The novelty lies in guaranteeing a bound on the number of safety violations, even in the absence of execution fairness (where existing algorithms may become permanently blocked due to both transient faults and crash failures). Considering the usefulness of vector clocks in facilitating various elementary synchronization building blocks in asynchronous systems without requiring remote replica synchronization, our analytical insights hold promise for designing other systems that cannot guarantee execution fairness.

• We show how to verify a large and complex system, named UniSUF, by employing problem decomposition techniques and rigorous reasoning. • We formally verify that UniSUF ensures security and correctness in terms of confidentiality, integrity, authenticity, freshness, order, and liveness. With the rise of software-defined vehicles (SDVs), where software governs most vehicle functions alongside enhanced connectivity, the need for secure software updates has become increasingly critical. Software vulnerabilities can severely impact safety, the economy, and society. In response to this challenge, Strandberg et al. [escar Europe, 2021] introduced the Unified Software Update Framework (UniSUF), designed to provide a secure update framework that integrates seamlessly with existing vehicular infrastructures. Although UniSUF has previously been evaluated regarding cybersecurity, these assessments have not employed formal verification methods. To bridge this gap, we perform a formal security analysis of UniSUF. We model UniSUF’s architecture and assumptions to reflect real-world automotive systems and develop a ProVerif-based framework that formally verifies UniSUF’s compliance with essential security requirements — confidentiality, integrity, authenticity, freshness, order, and liveness —demonstrating their satisfiability through symbolic execution. Our results demonstrate that UniSUF adheres to the specified security guarantees, ensuring the correctness and reliability of its security framework.

• This work provides the first self-stabilizing solution for the problem of constructing atomic snapshot objects, which can recover after the last occurrence of a transient fault (as well as node failures). • Our contribution is obtained via code transformation of earlier crash-tolerant algorithms for asynchronous message-passing systems prone to node failures. • This journal version extends our earlier conference papers by presenting the complete proofs for the proposed algorithms, and a completely new upper-bound on the operation completion time. A snapshot object simulates the behavior of an array of single-writer/multi-reader shared registers that can be read atomically. In 2018, Delporte-Gallet et al. proposed two fault-tolerant algorithms for snapshot objects in asynchronous crash-prone message-passing systems. Their first algorithm is non-blocking ; it allows snapshot operations to complete once all write operations have ceased. Their second algorithm allows snapshot operations to always terminate independently of write operations. The fault model of Delporte-Gallet et al. considers node failures (crashes). We aim at the design of even more robust snapshot objects. We do so through the lenses of self-stabilization —a very strong notion of fault-tolerance. In addition to Delporte-Gallet et al. ’s fault model, our self-stabilizing algorithms can recover after the occurrence of transient faults ; these faults represent arbitrary violations of the assumptions according to which the system was designed to operate (as long as the code stays intact). In particular, in this work, we propose self-stabilizing variations of Delporte-Gallet et al. ’s non-blocking algorithm and always-terminating algorithm. Our algorithms have similar communication costs to the ones by Delporte-Gallet et al. yet they eventually recover from the last occurrence of a transient fault. The main differences are that our proposal considers repeated gossiping of O ( ν ) bit messages, ν being the number of bits for encoding the object, and deals with bounded space (which is a prerequisite for self-stabilization). This facilitates recovery of the registers and sequence numbers after the occurrence of the last transient fault by guaranteeing consistency. We use Lamport’s happened-before relation to bound, when possible, the completion time of write and snapshot operations.

Federated learning (FL) enables collaborative training of machine learning models without sharing sensitive client data, making it a cornerstone for privacy-critical applications. However, FL faces the dual challenge of ensuring learning quality and robust privacy protection while keeping resource consumption low, particularly when using computationally expensive techniques such as homomorphic encryption (HE). In this work, we enhance an FL process that preserves privacy using HE by integrating it with synthetic data generation and an interleaving strategy. Specifically, our solution, named Alternating Federated Learning (Alt-FL), consists of alternating between local training with authentic data (authentic rounds) and local training with synthetic data (synthetic rounds) and transferring the encrypted and plaintext model parameters on authentic and synthetic rounds (resp.). Our approach improves learning quality (e.g., model accuracy) through datasets enhanced with synthetic data, preserves client data privacy via HE, and keeps manageable encryption and decryption costs through our interleaving strategy. We evaluate our solution against data leakage attacks, such as the DLG attack, demonstrating robust privacy protection. Also, Alt-FL provides 13.4% higher model accuracy and decreases HE-related costs by up to 48% with respect to Selective HE.

We formalize and solve a novel variation of the classic mutual exclusion problem that tolerates both process crashes and memory corruptions, and we propose the first solutions based on a novel failure detector.

Consensus, abstracting myriad problems in which processes must agree on a single value, is one of the most celebrated problems of fault-tolerant distributed computing. Consensus applications include fundamental services for the Cloud and Blockchain environments, and in such challenging environments, malicious behaviors are often modeled as adversarial Byzantine faults. At OPODIS 2010, Mostéfaoui and Raynal (in short, MR) presented a Byzantine-tolerant solution to consensus in which the decided value cannot be proposed only by Byzantine processes. MR has optimal resilience coping with up to t < n / 3 Byzantine nodes over n processes. MR provides this multivalued consensus object (which accepts proposals taken from a finite set of values), assuming the availability of a single binary consensus object (which accepts proposals taken from the set { 0 , 1 } ). This work, which focuses on multivalued consensus, aims to design an even more robust solution than MR. Our proposal expands MR's fault-model with self-stabilization, a vigorous notion of fault-tolerance. In addition to tolerating Byzantine, self-stabilizing systems can automatically recover after arbitrary transient-faults occur. These faults represent any violation of the assumptions according to which the system was designed to operate (provided that the algorithm code remains intact). To the best of our knowledge, we propose the first self-stabilizing solution for multivalued consensus for asynchronous message-passing systems prone to Byzantine failures. Our solution has an O ( t ) stabilization time from arbitrary transient faults.

We address the problem of Reliable Broadcast in asynchronous message-passing systems with n nodes, of which up to t are malicious (faulty), in addition to a message adversary that can drop some of the messages sent by correct (non-faulty) nodes. We present a Message-Adversary-Tolerant Byzantine Reliable Broadcast (MBRB) algorithm that communicates O(|m|+nκ) bits per node, where |m| represents the length of the application message and κ = Ω(log n) is a security parameter. This communication complexity is optimal up to the parameter κ. This significantly improves upon the state-of-the-art MBRB solution (Albouy, Frey, Raynal, and Taïani, TCS 2023), which incurs communication of O(n|m|+n²κ) bits per node. Our solution sends at most 4n² messages overall, which is asymptotically optimal. Reduced communication is achieved by employing coding techniques that replace the need for all nodes to (re-)broadcast the entire application message m. Instead, nodes forward authenticated fragments of the encoding of m using an erasure-correcting code. Under the cryptographic assumptions of threshold signatures and vector commitments, and assuming n > 3t+2d, where the adversary drops at most d messages per broadcast, our algorithm allows at least 𝓁 = n - t - (1 + ε)d (for any arbitrarily low ε > 0) correct nodes to reconstruct m, despite missing fragments caused by the malicious nodes and the message adversary.

International audience

Guerraoui proposed an indulgent solution for the binary consensus problem. Namely, he showed that an arbitrary behavior of the failure detector never violates safety requirements even if it compromises liveness. Consensus implementations are often used in a repeated manner. Dutta and Guerraoui proposed a zero-degrading solution, i.e., during system runs in which the failure detector behaves perfectly, a node failure during one consensus instance has no impact on the performance of future instances. Our study, which focuses on indulgent zero-degrading binary consensus, aims at the design of an even more robust communication abstraction. We do so through the lenses of self-stabilization—a very strong notion of fault-tolerance. In addition to node and communication failures, self-stabilizing algorithms can recover after the occurrence of arbitrary transient faults; these faults represent any violation of the assumptions according to which the system was designed to operate (as long as the algorithm code stays intact). This work proposes the first, to the best of our knowledge, self-stabilizing algorithm for indulgent zero-degrading binary consensus for time-free message-passing systems prone to detectable process failures. The proposed algorithm recovers within a finite time after the occurrence of the last arbitrary transient fault. Since the proposed solution uses an Ω failure detector, we also present the first, to the best of our knowledge, self-stabilizing asynchronous Ω failure detector, which is a variation on the one by Mostéfaoui, Mourgaya, and Raynal.

The multivalued consensus problem is a fundamental issue in fault-tolerant distributed computing. It encompasses a wide range of agreement problems where processes must unanimously decide on a specific value v ∈ V , with | V | ≥ 2 . Existing solutions that handle process crash failures simplify the multivalued consensus problem by reducing it to the binary consensus problem. Examples of such solutions include Mostéfaoui-Raynal-Tronel [IPL 2000] and Zhang-Chen [IPL 2009]. In this work, we aim to design an even more reliable solution by leveraging the concept of self-stabilization , which provides a strong form of fault tolerance. Self-stabilizing algorithms can recover from transient faults, which represent any deviation from the system's intended behavior (as long as the algorithm code remains intact) in addition to process and communication failures. To the best of our knowledge, this work presents the first self-stabilizing algorithm for multivalued consensus in asynchronous message-passing systems susceptible to process failures and transient faults. Our solution uses, at most, n concurrent invocations of binary consensus. This is another way we advance state-of-the-art solutions compared to previous non-self-stabilizing ones. For example, Mostéfaoui-Raynal-Tronel's solution requires an unbounded number of sequential invocations of binary consensus.

Abstract We study the problem of privately emulating shared memory in message-passing networks. The system includes clients that store and retrieve replicated information on N servers, out of which e are data-corrupting malicious . When a client accesses a data-corrupting malicious server, the data field of that server response might be different from the value it originally stored. However, all other control variables in the server reply and protocol actions are according to the server algorithm. For the coded atomic storage algorithms by Cadambe et al., we present an enhancement that ensures no information leakage and data-corrupting malicious fault-tolerance. We also consider recovery after the occurrence of transient faults that violate the assumptions according to which the system was designed to operate. After their last occurrence, transient faults leave the system in an arbitrary state (while the program code stays intact). We present a self-stabilizing algorithm, which recovers after the occurrence of transient faults. This addition to Cadambe et al. considers asynchronous settings as long as no transient faults occur. The recovery from transient faults that bring the system counters (close) to their maximal values may include the use of a global reset procedure, which requires the system run to be controlled by a fair scheduler. After the recovery period, the safety properties are provided for asynchronous system runs that are not necessarily controlled by fair schedulers. Since the recovery period is bounded and the occurrence of transient faults is extremely rare, we call this design criteria self-stabilization in the presence of seldom fairness. Our self-stabilizing algorithm uses a bounded amount of storage during asynchronous executions (that are not necessarily controlled by fair schedulers). To the best of our knowledge, we are the first to address privacy, data-corrupting malicious behavior, and self-stabilization in the context of emulating atomic shared memory in message-passing systems.

We study a well-known communication abstraction called Byzantine Reliable Broadcast (BRB). This abstraction is central in the design and implementation of fault-tolerant distributed systems, as many fault-tolerant distributed applications require communication with provable guarantees on message deliveries. Our study focuses on fault-tolerant implementations for message-passing systems that are prone to process-failures, such as crashes and malicious behavior. At PODC 1983, Bracha and Toueg, in short, BT, solved the BRB problem. BT has optimal resilience since it can deal with t

Fault-tolerant distributed applications require communication abstractions with provable guarantees on message deliveries. For example, Set-Constrained Delivery Broadcast (SCD-broadcast) is a communication abstraction for broadcasting messages in a manner that, if a process delivers a set of messages that includes m and later delivers a set of messages that includes m , no process delivers first a set of messages that includes m′ and later a set of messages that includes m.Imbs et al. proposed this communication abstraction and its first implementation. They have demonstrated that SCD-broadcast has the computational power of read/write registers and allows for an easy building of distributed objects such as snapshot objects and consistent counters. Imbs et al. focused on fault-tolerant implementations for asynchronous message-passing systems that are prone to process crashes. This paper aims to design an even more robust SCD-broadcast communication abstraction, namely a self-stabilizing SCD-broadcast. In addition to process and communication failures, self-stabilizing algorithms can recover after the occurrence of arbitrary transient faults; these faults represent any violation of the assumptions according to which the system was designed to operate (as long as the algorithm code stays intact).This work proposes the first self-stabilizing SCD-broadcast algorithm for asynchronous message-passing systems that are prone to process crash failures. The proposed self-stabilizing SCD-broadcast algorithm has an $\mathcal{O}(1)$ stabilization time (in terms of asynchronous cycles). The communication costs of our algorithm are similar to the ones of the non-self-stabilizing state-of-the-art. The main differences are that our proposal considers repeated gossiping of $\mathcal{O}(1)$ bits messages and deals with bounded space (which is a prerequisite for self-stabilization). We advance the state-of-the-art also by two new self-stabilizing applications: an atomic construction of snapshot objects and sequentially consistent counters.

A snapshot object simulates the behavior of an array of single-writer/multi-reader shared registers that can be read atomically. Delporte-Gallet et al. proposed two fault-tolerant algorithms for snapshot objects in asynchronous crash-prone message-passing systems. Their first algorithm is non-blocking; it allows snapshot operations to terminate once all write operations had ceased. It uses O(n) messages of O(n v) bits, where n is the number of nodes and v is the number of bits it takes to represent the object. Their second algorithm allows snapshot operations to always terminate independently of write operations. It incurs O(n^2) messages. The fault model of Delporte-Gallet et al. considers node failures (crashes). We aim at the design of even more robust snapshot objects. We do so through the lenses of self-stabilization---a very strong notion of fault-tolerance. In addition to Delporte-Gallet et al.'s fault model, a self-stabilizing algorithm can recover after the occurrence of transient faults; these faults represent arbitrary violations of the assumptions according to which the system was designed to operate (as long as the code stays intact). In particular, in this work, we propose self-stabilizing variations of Delporte-Gallet et al.'s non-blocking algorithm and always-terminating algorithm. Our algorithms have similar communication costs to the ones by Delporte-Gallet et al. and O(1) recovery time (in terms of asynchronous cycles) from transient faults. The main differences are that our proposal considers repeated gossiping of O(v) bits messages and deals with bounded space, which is a prerequisite for self-stabilization.

The vision of automated driving promises to have safer and more cost-efficient transport systems. Automated driving systems have to demonstrate high levels of dependability and affordability. Recent advances of new communication technologies, e.g., 5G, allow significant cost reduction of timely shared sensory information. However, the design of fault-tolerant automated driving systems remains an open challenge. This work considers the design of automated driving systems through the lenses of self-stabilization-a very strong notion of fault-tolerance. Our self-stabilizing algorithms guarantee, within a bounded period, recovery from a broad fault model and arbitrary state corruption. After this recovery period, our algorithms provide safe maneuver execution despite the presence of failures, such as unbounded periods of packet loss and timing failures as well as inaccurate sensory information and malicious behavior. We evaluate the proposed algorithms through a rigorous correctness proof and a worst-case analysis as well as a prototype that focuses on an intersection crossing protocol. We validate our prototype via computer simulations and a testbed implementation. Our preliminary results show a reduction in the number of vehicle collisions and dangerous situations.

We study a combinatorial optimization problem that is motivated by the scenario of autonomous cars driving on a multi-lane highway: some cars need to change lanes before the next intersection, and if there is congestion, cars need to slow down to make space for those who are changing lanes. There are two natural objective functions to minimize: (1) how long does it take for all traffic to clear the road, and (2) the total number of maneuvers. In this work, we present an approximation algorithm for solving these problems in the two-lane case and a hardness result for the multi-lane case.

By introducing programmability, automated verification, and innovative debugging tools, Software-Defined Networks (SDNs) are poised to meet the increasingly stringent dependability requirements of today's communication networks. However, the design of fault-tolerant SDNs remains an open challenge. This paper considers the design of dependable SDNs through the lenses of self-stabilization - a very strong notion of fault-tolerance. In particular, we develop algorithms for an in-band and distributed control plane for SDNs, called Renaissance, which tolerates a wide range of (concurrent) controller, link, and communication failures. Our self-stabilizing algorithms ensure that after the occurrence of an arbitrary combination of failures, (i) every non-faulty SDN controller can eventually reach any switch in the network within a bounded communication delay (in the presence of a bounded number of concurrent failures) and (ii) every switch is managed by at least one non-faulty controller. We evaluate Renaissance through a rigorous worst-case analysis as well as a prototype implementation (based on OVS and Floodlight), and we report on our experiments using Mininet.

Adopting distributed control planes is critical towards ensuring high availability and fault-tolerance of dependable Software-Defined Networks (SDNs). However, designing and bootstrapping a distributed SDN control plane is a challenging task, especially if to be done in-band, without a dedicated control network, and without relying on legacy networking protocols. One of the most appealing and powerful notions of fault-tolerance is self-organization and this paper discusses the possibility of self-organizing algorithms for in-band control planes.

Vehicle-to-vehicle (V2V) communication is a crucial component of the future autonomous driving systems since it enables improved awareness of the surrounding environment, even without extensive processing of sensory information. However, V2V communication is prone to failures and delays, so a distributed fault-tolerant approach is required for safe and efficient transportation. In this paper, we focus on the intersection crossing (IC) problem with autonomous vehicles that cooperate via V2V communications, and propose a novel distributed IC algorithm that can handle an unknown and large (yet finite) number of communication failures. Our analysis shows that both safety and liveness requirements are satisfied in all realistic situations. We also found, based on a real data set, that the crossing delay is only slightly increased even in the presence of highly correlated failures.

The performance of low-cost RTK (real-time kinematic) GPS receivers has been compared to a state-of-the-art system as well to each other. Both static and dynamic performances have been compared. The dynamic performance has been evaluated using a vehicle with driving robot on the AstaZero proving ground. The assembly of the low-cost RTK GPS receivers is presented, and the test set-ups described. Besides having a lower data output frequency, two of the low-cost receivers have static and dynamic performance not far from that of the state-of-the-art system.

We study the problem of privately emulating shared memory in message passing networks. The system includes $N$ servers, and at most e semi-Byzantine servers that can deviate from the algorithm by sending corrupted data. Moreover, at most f servers can fail and stop.

Ultra-wide bandwidth (UWB) systems allow for accurate positioning in environments where global navigation satellite systems may fail, especially when complemented with cooperative processing. While cooperative UWB has led to centimeter-level accuracies, the communication overhead is often neglected. We quantify how accuracy and delay trade off in a wide variety of operation conditions. We also derive the asymptotic scaling of accuracy and delay, indicating that, in some conditions, standard cooperation offers the worst possible tradeoff. Both avenues lead to the same conclusion: indiscriminately targeting increased accuracy incurs a significant delay penalty. Simple countermeasures can be taken to reduce this penalty and obtain a meaningful accuracy/delay trade-off.

The problem of local clock synchronization is studied in the context of media access control (MAC) protocols, such as time division multiple access (TDMA), for dynamic and wireless ad hoc networks. In the context of TDMA, local pulse synchronization mechanisms let neighboring nodes align the timing of their packet transmissions, and by that avoid transmission interferences between consecutive timeslots. Existing implementations for Vehicular Ad-Hoc Networks (VANETs) assume the availability of common (external) sources of time, such as base-stations or geographical positioning systems (GPS). This work is the first to consider autonomic design criteria, which are imperative when no common time sources are available, or preferred not to be used, due to their cost and signal loss. We present self-*pulse synchronization strategies. Their implementing algorithms consider the effects of communication delays and transmission interferences. We demonstrate the algorithms via extensive simulations in different settings including node mobility. We also validate these simulations in the MicaZ platform, whose native clocks are driven by inexpensive crystal oscillators. The results imply that the studied algorithms can facilitate autonomous TDMA protocols for VANETs.

Vehicular system designers often use simulation tools in order to prove vehicular systems. The computational complexity of detailed simulations limits the scale of such testings. Therefore, it is often the case that the first full-scale demonstrations of new concepts for vehicular systems are done in proving grounds and testing tracks. We propose Gulliver as a platform for studying vehicular systems on a large scale open source test-bed of low cost miniature vehicles that use wireless communication and are equipped with onboard sensors. Our approach provides a simpler yet detailed investigation of vehicular systems. This paper presents the platform with its design and a set of applications that could be demonstrated by Gulliver. Gulliver allows the design of vehicular systems to focus on the cyber-physical aspects of the studied problems. We expect that Gulliver will allow affordability and flexibility for a wider range of researchers to directly contribute to the development of future vehicular systems, such as greener transportation initiatives and zero fatality objectives.

Players in a game are assumed to be totally rational and absolutely smart. However, in reality all players may act in non-rational ways and may fail to understand and find their best actions. In particular, participants in social interactions, such as lotteries and auctions, cannot be expected to always find by themselves the "best-reply" to any situation. Indeed, agents may consult with others about the possible outcome of their actions. It is then up to the counselee to assure the rationality of the consultant's advice. We present a distributed computer system infrastructure, named rationality authority, that allows safe consultation among (possibly biased) parties. The parties' advices are adapted only after verifying their feasibility and optimality by standard formal proof checkers. The rationality authority design considers computational constraints, as well as privacy and security issues, such as verification methods that do not reveal private preferences. Some of the techniques resembles zero-knowledge proofs. A non-cooperative game is presented by the game inventor along with its (possibly intractable) equilibrium. The game inventor advises playing by this equilibrium and offers a checkable proof for the equilibrium feasibility and optimality. Standard verification procedures, provided by trusted (according to their reputation) verification procedures, are used to verify the proof. Thus, the proposed rationality authority infrastructure facilitates the applications of game theory in several important real-life scenarios by the use of computing systems.

We present an ongoing series of tests that explore the capabilities of un-augmented smart phones to serve as indoor navigation devices. We developed and tested a dead reckoning navigation application on an IPhone 3GS. It was found that the DRec application can count steps with more than 97% accuracy. This parameter, when multiplied with the user's personal step distance can be used to compute distance traveled. In initial tests DRec was able to compute the distance traveled with more than 90% accuracy. A dead reckoning test was also run, and initial results are promising.

Distributed algorithm designers often assume that system processes execute the same predefined software. Alternatively, when they do not assume that, designers turn to non-cooperative games and seek an outcome that corresponds to a rough consensus when no coordination is allowed. We argue that both assumptions are inapplicable in many real distributed systems, e.g., the Internet, and propose designing self-stabilizing and Byzantine fault-tolerant distributed game authorities. Once established, the game authority can secure the execution of any complete information game. As a result, we reduce costs that are due to the processes’ freedom of choice. Namely, we reduce the price of malice.

We introduce a self-stabilizing group communication system for ad hoc networks. The system design is based on a mobile agent, collecting and distributing information, during a random walk. Three possible settings for modeling the location of the mobile nodes (processors) in the ad hoc network are presented: slow location change, complete random change, and neighbors with probability. The group membership algorithm is based on a mobile agent collecting and distributing information. The new techniques support group membership and multicast, and also support resource allocation.

This paper presents a new abstraction for virtual infrastructure in mobile ad hoc networks. An AutonomousVirtual Mobile Node (AVMN) is a robust and reliable entity that is designed to cope with theinherent difficulties caused by processors arriving, leaving, and moving according to their own agendas,as well as with failures and energy limitations. There are many types of applications that may make useof the AVMN infrastructure: tracking, supporting mobile users, or searching for energy sources.The AVMN extends the focal point abstraction in [9] and the virtual mobile node abstraction in [10].The new abstraction is that of a virtual general-purpose computing entity, an automaton that can makeautonomous on-line decisions concerning its own movement. We describe a self-stabilizing implementationof this new abstraction that is resilient to the chaotic behavior of the physical processors and providesautomatic recovery from any corrupted state of the system.

No abstract available.

This paper presents the first (randomized) algorithm for implementing self-stabilizing group communication services in an asynchronous system. Our algorithm converges rapidly to legal behavior and is communication adaptive, namely, the communication volume is high when the system recovers from the occurrence of faults and is low once a legal state is reached. Communication adaptability is achieved by a new technique that combines transient fault detectors.

No abstract available.

We introduce a self-stabilizing group communication system for ad-hoc networks. The system design is based on random walks of mobile agents. Three possible settings for modeling the location of the processors in the ad-hoc network are presented; slow location change, complete random change, and neighbors with probability. The group membership algorithm is based on collecting and distributing information by a mobile agent. The new techniques support group membership and multicast, and also support resource allocation.